visit
由于一些不可预知的错误导致我一直WA 错误最后说
思路
方案一
假设终点在出发点右上方（这样假设只是为了方便）
假设向左走了a步，向右下了b布，那么相应的我们要向右走m+a，向上n+b步
总步数t 所以由多重集方案数可得
$ frac{t !}{a ! imes b! imes (n+a)! imes (m+b)!}$
这种方法要特殊处理
方案二
假设向上下一共走了i步
如果i超出了范围我们要往回走(i-n)/2步（自己在纸上画一下）
然后如果i-n除不开2那么这种情况是无解的
左右同理
得到式子
$ans=sumlimits_{i=n 2|i-n}^{t-m} C_{t}^{i} imes C_{i}^{frac{i-n}{2} } imes C_{t-i}^{frac{t-i-m}{2}}$
因为模数不一定为质数，但是几个质数乘积，所以我们要用先求出来分别模这几个质数结果，然后CRT合并
我犯的错误
我一开始看了吴迪的式子（$ frac{t !}{a ! imes b! imes (n+a)! imes (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 ") 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 ",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 ",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 ",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 "); continue; } else if(c%b){ printf("0 "); continue; } else{printf("ZenMeZheMeDuo ");continue;}; } if(b==0) { if((a<=0&&c>=0)||(a>=0&&c<=0)) { printf("0 "); continue; } else if(c%a){ printf("0 "); continue; } else {printf("ZenMeZheMeDuo ");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 ",x,y,a,b,c); if(c%g){printf("0 ");continue;} if(a*b<0) {printf("ZenMeZheMeDuo ");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 ",y,y2,x,c); if(ans<=65535) printf("%lld ",ans); else printf("ZenMeZheMeDuo "); } }
题目思路还是挺简单的就是一些恶心的特判
特判
首先$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$同号无穷多解