51Nod1362 搬箱子 排列组合,中国剩余定理

​​题目传送门 - 51Nod1362​​题意

题解

　　首先考虑枚举斜着走了几次。假设走了 $k$ 次，那么显然竖着走了 $n-k$ 次，将他们排列一下，有 $\binom{n}{k}$ 种排列。

　　设往下走 $k$ 次，往右走最多 $m$ 次的方案数为：

$$F_{n,m}=\sum_{i=0}^m \binom{i+n}{n}$$

　　则

$$\begin{eqnarray*}F_{n,m}&=&\sum_{i=0}^m \binom{i+n}{n}\\&=&\sum_{i=0}^{m} \left(\binom{i+n-1}{n}+\binom{i+n-1}{n-1}\right)\\&=&\sum_{i=1}^{m}\binom{(i-1)+n}{n}+\sum_{i=0}^{m} \binom{i+(n-1)}{(n-1)}\\&=&F_{n,m-1}+F_{n-1,m}\end{eqnarray*}$$

　　考虑计算边界情况的 $F$ 值，有：

$$\begin{cases}F_{i,0}=\binom{i}{i}=1\\F_{0,i}=\sum_{j=0}^{i}\binom{j}{j}=i+1\end{cases}$$

　　不难发现，

$$F_{n,m}=\binom{n+1}{m}$$

　　所以每一个 $F_{n,m}$ 都可以 $O(n)$ 来求，但是由于模数并不是大素数，所以我们需要分解模数并用互质情况下的 CRT 合并，所以要带一个 $\log$ 。

　　于是，最终答案为

$$\sum_{i=0}^{n}\binom{n}{i}\binom{n+m-i+1}{n+1}$$

　　总时间复杂度为 $O(n^2\log m)$ 。

　　由于我偷了个懒，没有预处理，所以我的代码的时间复杂度为 $O(n^2\log^2 m)$ 。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=805;
int n,m,X;
int p[20],q[20],cnt=0;
int C[N][N];
void Get_Small_C(int mod){
  memset(C,0,sizeof C);
  for (int i=0;i<=n;i++)
    C[i][i]=C[i][0]=1;
  for (int i=1;i<=n;i++)
    for (int j=1;j<i;j++)
      C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
void Get_Factors(int x){
  cnt=0;
  for (int i=2;i*i<=x;i++)
    if (x%i==0){
      p[++cnt]=i,q[cnt]=0;
      while (x%i==0)
        x/=i,q[cnt]++;
    }
  if (x>1)
    p[++cnt]=x,q[cnt]=1;
}
int Pow(int x,int y,int mod){
  int ans=1;
  for (;y;y>>=1,x=1LL*x*x%mod)
    if (y&1)
      ans=1LL*ans*x%mod;
  return ans;
}
int Phi(int p,int q){
  return (p-1)*Pow(p,q-1,X+1);
}
int Large_C(int n,int m,int p,int q){
  if (m>n||m<0)
    return 0;
  int pw=Pow(p,q,X+1),phi=Phi(p,q);
  int cntp=0,C=1;
  for (int i=1;i<=m;i++){
    int a=n-i+1,b=i;
    while (a%p==0)
      a/=p,cntp++;
    while (b%p==0)
      b/=p,cntp--;
    C=1LL*C*a%pw*Pow(b,phi-1,pw)%pw;
  }
  return 1LL*C*Pow(p,cntp,pw)%pw;
}
void ex_gcd(int a,int b,int &x,int &y){
  if (!b){
    x=1,y=0;
    return;
  }
  ex_gcd(b,a%b,y,x);
  y-=x*(a/b);
}
int CRT(int *v,int n){
  int A=0,M=1;
  for (int i=1;i<=n;i++){
    int a=v[i],m=Pow(p[i],q[i],X+1);
    int t=a-A,x,y;
    ex_gcd(M,m,x,y);
    x=1LL*x*t%m;
    A=(1LL*x*M+A)%(M*m);
    M*=m;
  }
  return (A+X)%X;
}
int Large_C(int n,int m){
  if (m>n||m<0)
    return 0;
  int res[20];
  for (int i=1;i<=cnt;i++)
    res[i]=Large_C(n,m,p[i],q[i]);
  return CRT(res,cnt);
}
int main(){
  while (~scanf("%d%d%d",&n,&m,&X)){
    Get_Small_C(X);
    Get_Factors(X);
    int ans=0;
    for (int i=0;i<=n;i++)
      ans=(1LL*C[n][i]*Large_C(n+m-i+1,n+1)+ans)%X;
    printf("%d\n",ans);
  }
  return 0;
}
/*
枚举斜着走了几次，然后推式子。 
*/