T2 visit
[组合数学][中国剩余定理]
一场考试难得见两个数学题
本来想矩阵快速幂，显然空间复杂度不行，主要是没时间，就没打
正解：
首先推波式子
1.$C_{t}^{k}$ 在t步中总共选出k步向上走，但最终只会走到m，到达m后，会又向下走k-m步，并会再向上走k-m步
2.$C_{t-k}^{k-m}$ 在剩下的t-k步中选出向下走的k-m步
3. 先介绍一个小技巧：eg 10 分成两个数，使两数之和为10，之差为4，
则大数（10+4）/2=7，小数（10-4）/2=3
$C_{t-2k+m}^{frac{t-2k+m+n}{2}}$ 此时还剩t-k-(k-m)=t-2k+m 步，这些用来分给向左和右的步数，因为最终要向右到n
所以向右的总步数-向左的总步数=n，由以上技巧
t-2k+m是和，n是差，相加再/2是就是向右的步数
在$t-2k+m$中选出向右的$frac{t-2k+m+n}{2}$步数
用向上，下，和左右的组合数相乘得到总步数
关键是k的范围：首先k>=m，否则上不去，
同理向右的$frac{t-2k+m+n}{2}$>=n
联立解得$kin[m,frac{t+m-n}{2}]$
合起来：$sumlimits_{k=m}^{frac{t+m-n}{2}}(C_{t}^{k} imes C_{t-k}^{k-m} imes C_{t-2k+m}^{frac{t-2k+m+n}{2}})$
如何实现？
1.对于mod是质数的情况，直接 预处理+lucas定理
2.若mod是由若干个质数相乘得到，将mod分解质因数，
对于每个质因子q[i]，原式对其取模得到的结果就是其余数，记做b[i]
那么问题就转化成了最终结果ans≡b[i](%p[i]) 在%mod情况下的线性同余方程组，用CRT求解即可
负数的情况变成正的来处理
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<vector> 5 #define int long long 6 using namespace std; 7 const int maxn=10000000; 8 int t; 9 vector<int>q; 10 int exgcd(int a,int b,int &x,int &y) 11 { 12 if(!b){x=1,y=0;return a;} 13 int d=exgcd(b,a%b,x,y); 14 int tmp=x;x=y;y=tmp-(a/b)*y; 15 return d; 16 } 17 int b[maxn+5]; 18 int crt(int mod) 19 { 20 int ans=0; 21 for(int i=0;i<q.size();i++) 22 { 23 int tmp=mod/q[i],x,y; 24 exgcd(tmp,q[i],x,y); 25 ans=(ans+tmp*x*b[i])%mod; 26 } 27 return (ans%mod+mod)%mod; 28 } 29 int inv[maxn+5],fac[maxn+5]; 30 void init(int mod) 31 { 32 fac[0]=fac[1]=1; 33 inv[0]=inv[1]=1; 34 for(int i=2;i<=t;i++) 35 { 36 fac[i]=fac[i-1]*i%mod; 37 inv[i]=(mod-mod/i)*inv[mod%i]%mod; 38 } 39 for(int i=2;i<=t;i++) 40 inv[i]=inv[i-1]*inv[i]%mod; 41 } 42 int C(int n,int m,int mod) 43 { 44 if(m>n) return 0; 45 return fac[n]*inv[m]%mod*inv[n-m]%mod; 46 } 47 int lucas(int n,int m,int mod) 48 { 49 if(!m) return 1; 50 return lucas(n/mod,m/mod,mod)*C(n%mod,m%mod,mod)%mod; 51 } 52 void divide(int n) 53 { 54 for(int i=2;i<=sqrt(n);i++) 55 { 56 if(n%i)continue; 57 q.push_back(i); 58 n/=i; 59 } 60 if(n>1)q.push_back(n); 61 } 62 signed main() 63 { 64 int ans=0,n,m,mod; 65 scanf("%lld%lld%lld%lld",&t,&mod,&n,&m); 66 if(n<0)n=-n; 67 if(m<0)m=-m; 68 divide(mod); 69 int st=m,en=(t+m-n)>>1; 70 if(q.size()==1) 71 { 72 init(mod); 73 for(int k=st;k<=en;k++) 74 ans=(ans+lucas(t,k,mod)*lucas(t-k,k-m,mod)%mod*lucas(t-2*k+m,(t-2*k+m+n)>>1,mod)%mod)%mod; 75 printf("%lld ",ans); 76 return 0; 77 } 78 for(int i=0;i<q.size();i++) 79 { 80 init(q[i]); 81 for(int k=st;k<=en;k++) 82 b[i]=(b[i]+lucas(t,k,q[i])*lucas(t-k,k-m,q[i])%q[i]*lucas(t-2*k+m,(t-2*k+m+n)>>1,q[i])%q[i])%q[i]; 83 } 84 printf("%lld ",crt(mod)); 85 }
“组合数取模”