TC SRM 585 (三)

const int MOD = 1000000007;
LL c[40*40][40*40];
LL dp[40][1300];
LL a[40*40][40];
class LISNumber {
public:
LL PowMod(LL a,LL b){
LL ret=1;
while(b){
if(b&1) ret=((LL)ret*a)%MOD;
a=((LL)a*a)%MOD;
b>>=1;
}
return ret;
}
int count(vector cardsnum, int K){
int n=cardsnum.size();
memset(dp,0,sizeof(dp));
memset(a,0,sizeof(a));
for(int i=1;i<=36*36;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
}
a[0][0]=1LL;
for(int i=0;i<=37*37;i++){
for(int j=0;j<=37;j++){
for(int k=0;k<=37&&j+k<=37;k++){
a[i+1][j+k]=(a[i+1][j+k]+a[i][j])%MOD;
}
}
}
LL sum=cardsnum[n-1];
dp[n-1][cardsnum[n-1]]=1LL;
for(int i=n-2;i>=0;i--){
for(int j=0;j<=sum&&j<=K;j++){
if(dp[i+1][j]==0) continue;
for(int k=0;k<=cardsnum[i]&&j+k<=K;k++){
if(k+j int t=cardsnum[i]-k;
LL tmp=((LL)c[j][t]*(LL)a[t+1+(sum-j)][k])%MOD;
dp[i][j+k]=(dp[i][j+k]+(LL)dp[i+1][j]*tmp)%MOD;
}
}
sum+=cardsnum[i];
}
return (int)dp[0][K];
}

};