Description

Solution

考虑这个式子的组合意义:

从 \(n*k\) 个球中取若干个球,使得球的数量 \(\%k=r\) 的方案数

可以转化为 \(DP\) 模型,设 \(f[i][j]\) 表示前 \(i\) 个步,取得球的数量 \(\%k=j\) 的方案数

\(f[i][j]=f[i-1][j]+f[i-1][j-1]\)

发现这个东西就是杨辉三角(胡话,此题无关)

这样就可以做 \(O(k^3log)\) 了,并且可以过了

网上还有一种做法:

设 \(f[i*2][a+b]=\sum f[i][a]*f[i][b]\)

然后矩阵就变成了一个行向量了,复杂度优化成了 \(O(k^2log)\)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=51;

int mod,k,r;ll n;

struct mat{

	int a[N];

	mat(){memset(a,0,sizeof(a));}

	inline mat operator *(const mat &p){

		mat ret;

		for(int i=0;i<k;i++)

			for(int j=0;j<k;j++)

				ret.a[(i+j)%k]=(ret.a[(i+j)%k]+1ll*a[i]*p.a[j])%mod;

		return ret;

	}

}S,T;

inline int qm(int x,int k){

	ll sum=1;

	while(k){

		if(k&1)sum=1ll*x*sum%mod;

		x=1ll*x*x%mod;k>>=1;

	}return sum;

}

int main(){

  freopen("pp.in","r",stdin);

  freopen("pp.out","w",stdout);

  cin>>n>>mod>>k>>r;

  if(k==1)printf("%d\n",qm(2,n)),exit(0);

  S.a[0]=1;S.a[1]=1;T=S;

  n=n*k-1;

  while(n){

	  if(n&1)S=S*T;

	  T=T*T;n>>=1;

  }

  printf("%d\n",S.a[r]);

  return 0;

}