davidwang's Blog

首先很容易想到DP,其次很容易想到是矩阵乘法，正常的玩法矩阵是 $$ q^n*P $$ 的，这个肯定玩不过去

然后就是想办法压抑下状态，首先我们知道我们关心的只是连续男生有A个的未知数两，所以可以改成n^q然后发现知道1和2的就可以知道3的所以可以存n^(q-1)然后发现不是所有的都可以比如说1个的有n个两个的有n个那肯定不可能出现所以状态就被压下去了

但是这道题这样依然很难在bzoj上通过，所以有一个矩阵乘法的小优化(虽然这个优化对一些矩阵会很慢，但是对于这样的转移矩阵来说就会快很多)

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <algorithm>
#include <cerrno>
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int mod = 1000000007;
const int Size = 200;
struct Matrix{
	int n;
	int x[Size][Size];
	Matrix(){ memset(x,0,sizeof(x)); }
	int *operator[](int A){ return x[A]; } 
}C,ret,A,B;
inline void mul(Matrix &A,Matrix &B,Matrix &ans){
	ans.n=A.n;
	memset(C.x,0,sizeof(C.x));
	for (int k=0;k<A.n;k++)
		for (int i=0;i<A.n;i++)
			if (A[i][k])
				for (int j=0;j<A.n;j++)
					if (B[k][j]) C[i][j]=(C[i][j]+(LL)A[i][k]*B[k][j])%mod;
	for (int i=0;i<A.n;i++)
		for (int j=0;j<A.n;j++) ans[i][j]=C[i][j];
}
inline void power(Matrix &A,LL B){
	memset(ret.x,0,sizeof(ret.x)); ret.n=A.n;
	for (int i=1;i<A.n;i++)
		ret[i][i]=1;
	while (B){
		if (B&1) mul(ret,A,ret);
		mul(A,A,A);
		B>>=1;
	}
}
pair<int,int>List[100];
int tot;
int n,q,p,c[11][11];
LL m;
inline void addtrans(Matrix &A,int j1,int a1,int a2,int j2,int b1,int b2,int num){
	if (j2>q) return;
//	printf("addtrans(%d,%d,%d,%d,%d,%d) %d\n",j1,a1,a2,j2,b1,b2,num);
	int pos1=lower_bound(List+1,List+tot+1,make_pair(a1,a2))-List;
	int pos2=lower_bound(List+1,List+tot+1,make_pair(b1,b2))-List;
	A[pos1*(q+1)+j1][pos2*(q+1)+j2]+=num;
}
inline void addtrans(Matrix &A,int j1,int a,int j2,int b,int num){
	if (j2>q) return;
	A[a*(q+1)+j1][b*(q+1)+j2]+=num;
}
inline void work2(){
	for (int i=0;i<=n;i++)
		for (int j=0;j+i<=n;j++)
			List[++tot]=make_pair(i,j);
	A.n=B.n=tot*(q+1)+q+1;
	for (int j=0;j<=q;j++)
		for (int a1=0;a1<=n;a1++)
			for (int a2=0;a1+a2<=n;a2++)
				for (int k1=0;k1<=a1;k1++)
					for (int k2=0;k2<=a2;k2++)
						addtrans(A,j,a1,a2,j+(k1+k2==n),n-k1-k2,k1,c[a1][k1]*c[a2][k2]);
	power(A,m);
	int p=lower_bound(List+1,List+tot+1,make_pair(n,0))-List;
	B[0][p*(q+1)]=1;
	mul(B,ret,B);
	int ans=0;
	for (int i=0;i<B.n;i++) ans=(ans+B[0][i])%mod;
	printf("%d\n",ans);
}
	
inline void work1()
{
	A.n=B.n=n*(q+1)+(q+1);
	for (int j=0;j<=q;j++)
		for (int i=0;i<=n;i++)
			for (int k=0;k<=i;k++)
				addtrans(A,j,i,j+(k==n),n-k,c[i][k]);
	power(A,m);
	B[0][n*(q+1)]=1;
	mul(B,ret,B);
	int ans=0;
	for (int i=0;i<B.n;i++) ans=(ans+B[0][i])%mod; 
	printf("%d\n",ans);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("line.in","r",stdin);
	freopen("line.out","w",stdout);
#endif
	n=read(); scanf("%lld",&m),p=read(),q=read();
	c[0][0]=1;
	for (int i=1;i<=n;i++){
		c[i][0]=1;
		for (int j=1;j<=i;j++)
			c[i][j]=c[i-1][j]+c[i-1][j-1];
	}
	if (p==0){ printf("0\n"); return 0; }
	if (p==1){ printf("1\n"); return 0; }
	if (p==2){ work1(); return 0; }
	work2(); return 0;
}