[HDU3944]DP? （组合数学Lucas定理）

题目描述

传送门
题意：求在杨辉三角中从(0,0)走到(n,m)路上权值最小的方案%p的值。p为质数。

题解

杨辉三角是对称的，所以我们只考虑目标点在对称轴左边的情况
观察杨辉三角，可以发现一定是顺着一些1往下走然后斜着走到目标点
即 Cmn+Cm−1n−1+Cm−2n−2+...+C1n−m+1+Cn−m,0+n−m
我发现这个式子可以用我昨天刚学会的方法化简
就是利用 Cji=Cji−1+Cj−1i−1 ，然后把 C0n−m 写成 C0n−m+1 ，然后和 C1n−m+1 合并变成 C1n−m+2 ，然后再用这个和 C2n−m+2 合并
最后的答案 Cmn+Cm−1n−1+Cm−2n−2+...+C1n−m+1+Cn−m,0+n−m=Cmn+1+n−m
利用Lucas定理可以快速地求解 Cmn%p
不过这题数据组数太多，每一次预处理阶乘不行。由于1~10000内的质数只有1229个，可以预先预处理出来所有质数的阶乘，然后算的时候直接用

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

int Case,n,m,Mod;
int mul[1300][10005],prime[1300],p[10005],loc[100005];

void get_p()
{
for (int i=2;i<=10000;++i)
    {
if (!p[i]) prime[++prime[0]]=i;
for (int j=1;j<=prime[0]&&i*prime[j]<=10000;++j)
        {
            p[i*prime[j]]=1;
if (i%prime[j]==0) break;
        }
    }
for (int i=1;i<=prime[0];++i)
    {
        loc[prime[i]]=i;
        mul[i][0]=1;
for (int j=1;j<=prime[i];++j)
            mul[i][j]=mul[i][j-1]*j%prime[i];
    }
}
int fast_pow(int a,int p)
{
int ans=1;
for (;p;p>>=1,a=a*a%Mod)
if (p&1)
            ans=ans*a%Mod;
return ans;
}
int inv(int x)
{
return fast_pow(x,Mod-2);
}
int C(int n,int m)
{
if (m>n) return 0;
return mul[loc[Mod]][n]*inv(mul[loc[Mod]][m]*mul[loc[Mod]][n-m]%Mod)%Mod;
}
int lucas(int n,int m)
{
int ans=1;
for (;m;n/=Mod,m/=Mod)
 ans=ans*C(n%Mod,m%Mod)%Mod;
 return ans;
}
int main()
{
 get_p();
 while (~scanf("%d%d%d",&n,&m,&Mod))
 {
 if (m>n/2) m=n-m;
printf("Case #%d: %d\n",++Case,(lucas(n+1,m)+n-m)%Mod);
    }
}