【SHOISXOI2017】bzoj4870 组合数问题_综合

需要看出来这个公式的实际意义，因为 $r \lt k$ ，实际上就是问 $n$ 个数中选 $r(mod k)$ 个数的方案数。这样就可以dp了。不难写出裸的方程

d p [i] [j] = d p [i ? 1] [j] + d p [i ? 1] [j ? 1]

$dp[i][j]=dp[i-1][j]+dp[i-1][j-1]$

这个方程长得很好看，一定是可以优化的。可以发现

d p [i + j] [(x + y) % k] + = d p [i] [x] ? d p [j] [y]

$dp[i+j][(x+y)\% k]+=dp[i][x]*dp[j][y]$
因此可以对dp数组进行快速幂。

#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
int n,p,k,r;
int add(int x,int y)
{x+=y;return x>=k?x-k:x;
}
struct Dp
{int a[55];Dp operator * (const Dp &d) const{Dp ret;for (int i=0;i<k;i++) ret.a[i]=0;for (int i=0;i<k;i++)for (int j=0;j<k;j++)ret.a[add(i,j)]=(ret.a[add(i,j)]+(LL)a[i]*d.a[j])%p;return ret;}
}base,ans;
int main()
{//freopen("problem.in","r",stdin);//freopen("problem.out","w",stdout);scanf("%d%d%d%d",&n,&p,&k,&r);ans.a[0]=base.a[0]=1;base.a[k==1?0:1]++;for (LL i=(LL)n*k;i;i>>=1,base=base*base)if (i&1) ans=ans*base;printf("%d\n",ans.a[r]);
}