NOIP模拟测试7「方程的解·visit」
归档于 2019-07-22 19:23
visit
由于一些不可预知的错误导致我一直WA 错误最后说
思路
方案一
假设终点在出发点右上方（这样假设只是为了方便）
假设向左走了a步，向右下了b布，那么相应的我们要向右走m+a，向上n+b步
总步数t 所以由多重集方案数可得
$ \frac{t !}{a !\times b! \times (n+a)! \times (m+b)!}$
这种方法要特殊处理
方案二
假设向上下一共走了i步
如果i超出了范围我们要往回走(i-n)/2步（自己在纸上画一下）
然后如果i-n除不开2那么这种情况是无解的
左右同理
得到式子
$ans=\sum\limits_{i=n 2|i-n}^{t-m} C_{t}^{i}\times C_{i}^{\frac{i-n}{2}
}\times C_{t-i}^{\frac{t-i-m}{2}}$
因为模数不一定为质数，但是几个质数乘积，所以我们要用先求出来分别模这几个质数结果，然后CRT合并
我犯的错误
我一开始看了吴迪的式子（$ \frac{t !}{a !\times b! \times (n+a)! \times
(m+b)!}$），他的式子会发生另外一些不可预知的错误，模小数时他的式子会爆炸（$n!$中$n$比模数大时会发生另外一些错误）
然后我一开始没发现这个错误，发现他的式子跟我的差不多就开始打了，然后我就挂了。
然后我又自己推了一个式子用线性求逆元发现还是一直WA
最后wwb调了很长时间还是WA 最后进行了一番大改终于A了。
我用老套路控制变量（用A的代码一段一段替换WA的代码）发现线性求逆元爆炸了。
这里线性求逆元并不是我写错了，或者推错了
jie[0]=1;
ni[0]=1;
for(ll j=1;j<=t;j++)
jie[j]=jie[j-1]*j%w[i];
ni[t]=meng(jie[t],w[i]-2,i);
for(ll j=t-1;j>=1;j--)
ni[j]=ni[j+1]*(j+1)%w[i];
观察这段代码，首先如果jie里的j比w大那么他的阶乘取完模之后都为0，（前面有不是0的阶乘）
而ni 从t开始算的话如果最后一位为0那么这样递推算出来所有的逆元都为0
然而ni<w的一部分不是0 所以就错了
警醒
代码
#include<bits/stdc++.h>
#define ll long long
#define A 2000000
#define py printf("f**k\n")
ll a[A],b[A],k,p,n,m,t,num=0;
ll w[A],q[A],v[A],jie[A],ni[A];
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1;
y=0;
return a;
}
ll gcd=exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
return gcd;
}
void getprime(ll x){
for(ll i=2;i<=sqrt(x);i++)
{
if(x%i==0)
{
while(x%i==0)
{
x=x/i;
}
w[++w[0]]=i;
}
}
if(x!=1) w[++w[0]]=x;
return ;
}
ll meng(ll x,ll k,ll cix){
ll ans=1;
for(;k;k>>=1,x=x*x%w[cix])
if(k&1)
ans=ans*x%w[cix];
return ans;
}
ll china(){
ll x,y,a=0,m,n=1;
for(ll i=1;i<=w[0];i++)
n*=w[i];
for(ll i=1;i<=w[0];i++){
m=n/w[i];
exgcd(w[i],m,x,y);
y%=w[i];
a=(a+y*m*b[i])%n;
}
return (a+n)%n;
}
ll jic(ll n,ll m,ll cix){
if(m>n) return 0;
if(m==0) return 1;
return jie[n]%w[cix]*meng(jie[m]*jie[n-m]%w[cix],w[cix]-2,cix)%w[cix];
}
ll lucas(ll n,ll m,ll cix){
if(m>n)return 0;
if(n==0)return 1;
return jic(n%w[cix],m%w[cix],cix)*lucas(n/w[cix],m/w[cix],cix)%w[cix];
}
using namespace std;
int main()
{
scanf("%lld%lld",&t,&p);
scanf("%lld%lld",&n,&m);
getprime(p);
n=abs(n),m=abs(m);
for(ll i=1;i<=w[0];i++){
jie[0]=1;
ni[0]=1;
for(ll j=1;j<=t;j++)
jie[j]=jie[j-1]*j%w[i];
ni[t]=meng(jie[t],w[i]-2,i);
for(ll j=t-1;j>=1;j--)
ni[j]=ni[j+1]*(j+1)%w[i];
for(ll j=n;j<=t-m;j++){
if((j-n)%2) continue;
if((t-j-m)%2) continue;
ll t1=lucas(t,j,i),t2=lucas(j,(j-n)/2,i),t3=lucas(t-j,(t-j-m)/2,i);
b[i]=(b[i]+t1*t2%w[i]*t3)%w[i];
}
}
cout<<china()<<endl;
}
方程的解
各种傻逼特判，判错一个就40
思路：
思路有两种
一，
首先求出来左右边界然后拿右边界减左边界，非常简单，按照解方程的方法求即可
代码（我没打出来一直40分，这里是nc的代码）
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
ll T,a,b,c,x,y;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;y=0;
return a;
}
ll d=exgcd(b,a%b,x,y);
ll tmp=x;
x=y;
y=tmp-a/b*y;
return d;
}
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld%lld",&a,&b,&c);
ll d=exgcd(a,b,x,y);
ll l=floor(1.0*c/b*(-x)),r=ceil(1.0*c/a*y);
ll k=r-l-1;
if(a==0&&b==0)
{
if(c==0)
{
puts("ZenMeZheMeDuo");
continue;
}
else
{
puts("0");
continue;
}
}
if((c%d))
{
puts("0");
continue;
}
if(1LL*a*b<0)
{
puts("ZenMeZheMeDuo");
continue;
}
if(a==0)
{
if(1LL*b*c>0) puts("ZenMeZheMeDuo");
else puts("0");
continue;
}
if(b==0)
{
if(1LL*a*c>0) puts("ZenMeZheMeDuo");
else puts("0");
continue;
}
if(k<0)
{
puts("0");
continue;
}
if(k>65535) puts("ZenMeZheMeDuo");
else printf("%lld\n",k);
}
return 0;
}
二，
求出来ymax 再求出来ymin 再/a
非常简单的思路（虽然我觉得第一个更简单）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 100000
ll a,b,x,y,c,t;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;y=0;
return a;
}
ll c=exgcd(b,a%b,x,y);
ll z=x;
x=y;y=z-y*(a/b);
// printf("x=%lld y=%lld\n",x,y);
return c;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld%lld",&a,&b,&c);
// printf("a=%lld b=%lld\n",a,b);
x=0,y=0;
if(a<0&&b<0) a=-a,b=-b,c=-c;
if(a==0)
{
if((b<=0&&c>=0)||(b>=0&&c<=0))
{
printf("0\n");
continue;
}
else if(c%b){
printf("0\n");
continue;
}
else{printf("ZenMeZheMeDuo\n");continue;};
}
if(b==0)
{
if((a<=0&&c>=0)||(a>=0&&c<=0))
{
printf("0\n");
continue;
}
else if(c%a){
printf("0\n");
continue;
}
else {printf("ZenMeZheMeDuo\n");continue;};
}
ll g=exgcd(a,b,x,y),ans=0;
x*=c/g,y*=c/g;
// printf("%lld %lld a=%lld b=%lld c=%lld\n",x,y,a,b,c);
if(c%g){printf("0\n");continue;}
if(a*b<0)
{printf("ZenMeZheMeDuo\n");continue;}
a/=g,b/=g,c/=g;x%=b;
while(x<=0) x+=b;
y=(c-a*x)/b;
ll y2=y%a;
while(y2<=0) y2+=a;
ans=(y-y2)/a+1;
if(y2>y) ans=0;
// printf("y=%lld y2=%lld x=%lld c=%lld\n",y,y2,x,c);
if(ans<=65535)
printf("%lld\n",ans);
else
printf("ZenMeZheMeDuo\n");
}
}
题目思路还是挺简单的就是一些恶心的特判
特判
首先$c \mod gcd！=0$时无解
然后$a，b$异号时无穷多解
$a$为$0$，$b$为$0$，$c$为$0$时无穷多解
$a$为$0$ $b$为$0$ $c$不为$0$ 无解
$ymax<ymin$无解
$a==0$ $ b,c$异号无解
$a==0$ $ b,c$同号无穷多解
$b==0$ $ a,c$异号无解
$b==0$ $ a,c$同号无穷多解