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

╰半夏微凉° 2021-11-22 05:02 321阅读 0赞

考试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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<cstdio>
     3 #include<algorithm>
     4 #include<cmath>
     5 #include<cstring>
     6 #include<vector>
     7 #include<queue>
     8 #define int long long
     9 using namespace std;
    10 const int N=305;
    11 int flag=0;int t,n,m;
    12 int dp[N][N][N];
    13 int prime[N],a[N],inv[100005],res[N];
    14 int fac[100005];
    15 int qpow(int a,int b,int p){
    16     int ans=1;
    17     while(b){
    18         if(b&1) ans=ans*a%p;
    19         b>>=1;
    20         a=a*a%p;
    21     }
    22     return ans%p;
    23 }
    24 int C(int n,int m,int p){
    25     if(n<m) return 0;
    26     else return fac[n]%p*qpow(fac[n-m]*fac[m]%p,p-2,p)%p;
    27 }
    28 int lucas(int a,int b,int p){
    29     if(!b) return 1;
    30     else return lucas(a/p,b/p,p)%p*C(a%p,b%p,p)%p; 
    31 }
    32 void divide(int p){
    33     for(int i=2;i<=sqrt(p);i++){
    34         if(p%i==0){
    35             flag++;
    36             prime[flag]=i;
    37             p/=i;
    38         }
    39     }
    40     if(p>1) prime[++flag]=p;
    41 }
    42 int exgcd(int a,int b,int &x,int &y){
    43     int t;
    44     if(!b){
    45         x=1;y=0;return a;
    46     }
    47     t=exgcd(b,a%b,x,y);
    48     t=x;
    49     x=y;
    50     y=t-a/b*y;
    51 }
    52 int CRT(){
    53     int ans=0;
    54     int M=1;
    55     for(int i=1;i<=flag;i++) M*=prime[i];
    56     for(int i=1;i<=flag;i++){
    57         ans=(ans+M/prime[i]*res[i]%M*qpow(M/prime[i],prime[i]-2,prime[i])%M)%M;
    58     }
    59     return ans;
    60 }
    61 int init(int p){
    62     int minn=min(p-1,t);
    63     fac[0]=1;
    64     for(int i=1;i<=minn;i++){
    65         fac[i]=fac[i-1]*i%p;
    66     }
    67 }
    68 signed main(){
    69     int p;
    70     scanf("%lld%lld%lld%lld",&t,&p,&n,&m);
    71     m=abs(m);n=abs(n);
    72     divide(p);
    73     if(t<=100){
    74         int dd=105;
    75         dp[0][dd][dd]=1;
    76         for(int i=1;i<=t;i++){
    77             for(int j=-t;j<=t;j++){
    78                 for(int k=-t;k<=t;k++){
    79                     dp[i][j+dd][k+dd]=(dp[i][j+dd][k+dd]+dp[i-1][j+1+dd][k+dd]+dp[i-1][j+dd][k+1+dd]+dp[i-1][j-1+dd][k+dd]+dp[i-1][j+dd][k-1+dd])%p;
    80                 }
    81             }
    82         }
    83         printf("%lld",dp[t][n+dd][m+dd]);
    84         return 0;
    85     }
    86     int ans=0;
    87     fac[0]=1;
    88     //for(int i=1;i<=100005;i++) fac[i]=fac[i-1]*i%p;
    89     for(int i=1;i<=flag;i++){
    90         init(prime[i]);
    91         for(int k=n;k<=t-m;k+=2){
         //i+=2
    92             res[i]=(res[i]+lucas(t,k,prime[i])*lucas(k,(k-n)/2,prime[i])%p*lucas(t-k,(t-m-k)/2,prime[i]))%p;
    93         }
    94     }
    95     printf("%lld",CRT()%p);
    96 }

转载于:https://www.cnblogs.com/leom10/p/11228647.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211122/673959c996744596b351f2cfc7827a4f.png