HZOJ 20190722 visit （组合数学+数论）

考试T2，考试时打了个$O(n^3)$dp暴力，思路还是很好想的，但细节也不少，然后滚动数组没清空，而且题又看错了，只得了10pts，真是血的教训。

题解：

其实看数据范围，给出了模数是否为质数，其实应该能推测出这是道数学题（但是不会推式子啊）

我们仔细分析一下问题，我们设$ri,le,up ,down$分别为向右左上下走的步数，且总步数为T，然后我们只要知道，向一个方向走的步数就能得到其他的，但是我们发现光凭一个是求不出的，我们再转化一下思路，我们设在上下方向走的步数为$k$,则$up+down=k$,然后又因为他最后必须走到$(n,m)$，所以向上走的步数减去向下走的步数为$m$,即$up-down=m$，同理我们可以求出$ri$与$le$的关系，同样是两个方程，这样我们就可以通过枚举$k$，来得到向各个方向走的步数，这样就能列出组合数的式子了，即：

$\sum \limits_{k=m}^{t-n}C_t^k*C_k^{\frac{k-m}{2}}*C_{n-k}^{\frac{t-k-n}{2}}$

这题貌似到这里就结束了，但是我们注意到他的模数$p$并不一定是一个质数，所以我们用普通lucas是求不出来的，而ex_lucas又过于难写，且运行慢，其实是因为我不会哪又要怎么办呢，我们看他的数据范围中说模数p分解质因数后的每个质因子的次数都为1，那么我们就可以利用这个性质，先用普通lucas求出答案对每个质因子答案，然后用CRT合并即可。

要注意的几点：对于每个质因子求答案时都要处理一遍阶乘表，不然就会不对

一定要多取模，尤其是连乘的时候，不然很容易崩

　　　　　　　枚举k时要$k+=2$因为他在上下方向或左右方向的变化量不可能为1

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 #include<vector>

 #include<queue>

 #define int long long

 using namespace std;

 const int N=;

 int flag=;int t,n,m;

 int dp[N][N][N];

 int prime[N],a[N],inv[],res[N];

 int fac[];

 int qpow(int a,int b,int p){

     int ans=;

     while(b){

         if(b&) ans=ans*a%p;

         b>>=;

         a=a*a%p;

     }

     return ans%p;

 }

 int C(int n,int m,int p){

     if(n<m) return ;

     else return fac[n]%p*qpow(fac[n-m]*fac[m]%p,p-,p)%p;

 }

 int lucas(int a,int b,int p){

     if(!b) return ;

     else return lucas(a/p,b/p,p)%p*C(a%p,b%p,p)%p;

 }

 void divide(int p){

     for(int i=;i<=sqrt(p);i++){

         if(p%i==){

             flag++;

             prime[flag]=i;

             p/=i;

         }

     }

     if(p>) prime[++flag]=p;

 }

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

     int t;

     if(!b){

         x=;y=;return a;

     }

     t=exgcd(b,a%b,x,y);

     t=x;

     x=y;

     y=t-a/b*y;

 }

 int CRT(){

     int ans=;

     int M=;

     for(int i=;i<=flag;i++) M*=prime[i];

     for(int i=;i<=flag;i++){

         ans=(ans+M/prime[i]*res[i]%M*qpow(M/prime[i],prime[i]-,prime[i])%M)%M;

     }

     return ans;

 }

 int init(int p){

     int minn=min(p-,t);

     fac[]=;

     for(int i=;i<=minn;i++){

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

     }

 }

 signed main(){

     int p;

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

     m=abs(m);n=abs(n);

     divide(p);

     if(t<=){

         int dd=;

         dp[][dd][dd]=;

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

             for(int j=-t;j<=t;j++){

                 for(int k=-t;k<=t;k++){

                     dp[i][j+dd][k+dd]=(dp[i][j+dd][k+dd]+dp[i-][j++dd][k+dd]+dp[i-][j+dd][k++dd]+dp[i-][j-+dd][k+dd]+dp[i-][j+dd][k-+dd])%p;

                 }

             }

         }

         printf("%lld",dp[t][n+dd][m+dd]);

         return ;

     }

     int ans=;

     fac[]=;

     //for(int i=1;i<=100005;i++) fac[i]=fac[i-1]*i%p;

     for(int i=;i<=flag;i++){

         init(prime[i]);

         for(int k=n;k<=t-m;k+=){//i+=2

             res[i]=(res[i]+lucas(t,k,prime[i])*lucas(k,(k-n)/,prime[i])%p*lucas(t-k,(t-m-k)/,prime[i]))%p;

         }

     }

     printf("%lld",CRT()%p);

 }

巴特西

HZOJ 20190722 visit （组合数学+数论）

最新文章

热门文章