模拟7题解 T2visit

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

　　　　　　　　联立解得$k\in[m,\frac{t+m-n}{2}]$

合起来：$\sum\limits_{k=m}^{\frac{t+m-n}{2}}(C_{t}^{k}\times C_{t-k}^{k-m}\times 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求解即可

负数的情况变成正的来处理

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 #define int long long

 using namespace std;

 const int maxn=;

 int t;

 vector<int>q;

 int exgcd(int a,int b,int &x,int &y)

 {

     if(!b){x=,y=;return a;}

     int d=exgcd(b,a%b,x,y);

     int tmp=x;x=y;y=tmp-(a/b)*y;

     return d;

 }

 int b[maxn+];

 int crt(int mod)

 {

     int ans=;

     for(int i=;i<q.size();i++)

     {

         int tmp=mod/q[i],x,y;

         exgcd(tmp,q[i],x,y);

         ans=(ans+tmp*x*b[i])%mod;

     }

     return (ans%mod+mod)%mod;

 }

 int inv[maxn+],fac[maxn+];

 void init(int mod)

 {

     fac[]=fac[]=;

     inv[]=inv[]=;

     for(int i=;i<=t;i++)

     {

         fac[i]=fac[i-]*i%mod;

         inv[i]=(mod-mod/i)*inv[mod%i]%mod;

     }

     for(int i=;i<=t;i++)

         inv[i]=inv[i-]*inv[i]%mod;

 }

 int C(int n,int m,int mod)

 {

     if(m>n)  return ;

     return fac[n]*inv[m]%mod*inv[n-m]%mod;

 }

 int lucas(int n,int m,int mod)

 {

     if(!m)    return ;

     return lucas(n/mod,m/mod,mod)*C(n%mod,m%mod,mod)%mod;

 }

 void divide(int n)

 {

     for(int i=;i<=sqrt(n);i++)

     {

         if(n%i)continue;

         q.push_back(i);

         n/=i;

     }

     if(n>)q.push_back(n);

 }

 signed main()

 {

     int ans=,n,m,mod;

     scanf("%lld%lld%lld%lld",&t,&mod,&n,&m);

     if(n<)n=-n;

     if(m<)m=-m;

     divide(mod);

     int st=m,en=(t+m-n)>>;

     if(q.size()==)

     {

         init(mod);

         for(int k=st;k<=en;k++)

             ans=(ans+lucas(t,k,mod)*lucas(t-k,k-m,mod)%mod*lucas(t-*k+m,(t-*k+m+n)>>,mod)%mod)%mod;

         printf("%lld\n",ans);

         return ;

     }

     for(int i=;i<q.size();i++)

     {

         init(q[i]);

         for(int k=st;k<=en;k++)

             b[i]=(b[i]+lucas(t,k,q[i])*lucas(t-k,k-m,q[i])%q[i]*lucas(t-*k+m,(t-*k+m+n)>>,q[i])%q[i])%q[i];

     }

     printf("%lld\n",crt(mod));

 }

“组合数取模”

巴特西

模拟7题解 T2visit

T2 visit

[组合数学][中国剩余定理]

首先推波式子

如何实现？

最新文章

热门文章