【GDOI2018模拟7.9】组合数问题

Description

Input

四个数n,p,k,r

Output

一个整数表示答案

Sample Input

input 1: 2 10007 2 0 input 2: 20 10007 20 0

Sample Output

output 1: 8 output 2: 176

Data Constraint

Solution

这个出题人很良心啊，这么多可以水分的数据范围 直接上正解 考虑此题中C的意义 就是选了一堆物品，数量%k=r的方案数 那么考虑DP 设 f[i][j] 表示前i个数选的数量%k=j的方案数 那么 f[i][j+1]=f[i][j]+f[i][j−1] 即这一次是否选两种方式转移 注意，这里的-1是%k意义下的-1 那么这个DP可以用矩阵乘法优化，然后就可以过了 还有一种优化：可以发现这个DP满足结合律，所以可以直接对DP方程进行快速幂

Code

#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(ll i=a;i<=b;i++) #define N 60 #define ll long long using namespace std; ll a[N][N],b[N][N],c[N][N],n,m,mo,k,r,ans=0; void cl() { fo(i,0,n) fo(j,0,n) c[i][j]=a[i][j],a[i][j]=0; } void ch1() { cl(); fo(i,0,n) fo(j,0,n) fo(k,0,n) a[i][k]=(a[i][k]+c[i][j]*b[j][k])%mo; } void ch() { cl(); fo(i,0,n) fo(j,0,n) fo(k,0,n) a[i][k]=(a[i][k]+c[i][j]*c[j][k])%mo; } void mi(ll x) { if(x<=1) return; fo(i,0,n) fo(j,0,n) b[i][j]=a[i][j]; mi(x/2); ch(); if(x%2==1) ch1(); } ll mi1(ll a,ll b) { if(b==0) return 1; if(b==1) return a; ll k=mi1(a,b/2); k=(k*k)%mo; if(b%2==1) k=(k*a)%mo; return k; } ll C(ll m,ll n) { double jy=1,k=n; fo(i,m-n+1,m) { if(k>0)jy=jy*i/k; k--; } return jy; } int main() { scanf("%lld%lld%lld%lld",&m,&mo,&k,&r); if(k==1) { ans=mi1(2,m); fo(i,0,r-1) ans=(ans-C(m,i)+mo)%mo; printf("%lld",ans); return 0; } memset(a,0,sizeof(a)); fo(i,0,k-1) { fo(j,i,min(i+1,k-1)) a[i][j]=1; } a[k-1][0]=1; n=k-1;mi(k*m); fo(i,0,n) fo(j,0,n) b[i][j]=a[i][j],a[i][j]=0; a[0][0]=1; ch1(); printf("%lld",a[0][r%k]); }