有N个字母,每个字母的数量不定。用这N个字母组成一个长为M的串,并且规定这个串中每个字母能出现的次数。求这样的串的总数。
Input
每组输入数据的第一行有两个数字N,M。接下来有N行,每行的第一个数k表示对应字母可以出现的种数,接下来的k个数表示该字母可以在串中出现的个数。其中0表示可以不出现。如测试数据,第一个2表示有”A”“B”两个字母,第二个2表示求一个长度为2的串,第二行的第一个数3表示后面有3个数字,0,1,2分别表示字母”A”在这个串中可以出现0次,1次,2次,第三行表示字母”B”可以出现的次数。则这样的串有”AB”,”BA”,”AA”3种。
Output
对应每组输入,输出满足要求的串的总数。(输出结果不会超出2^63)
Sample Input
2 2
3 0 1 2
2 0 1
Sample Output
3
排列组合以及dp(递推?)的一道题
dp[i]表示长度为i的字符串可以有多少种组合情况
然后递推公式是
dp[j+s[i][k]]=dp[j]×c[m-j][s[i][k]]
也就是j的长度再加上第i个字符的第k种可能的长度,就等于原来j长度的情况乘以从m-j个剩余空间中选出s[i][k]个字符的种类
代码:
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define _clr(x,a) memset(x,a,sizeof(x));
using namespace std;
typedef long long ll;
const int MAXN=1000;
ll C[MAXN][MAXN];
ll s[MAXN][MAXN];
ll dp[MAXN];
void Init(){
for(int i=1;i<MAXN;i++){
C[i][0]=C[1][1]=1;
for(int j=1;j<=i;j++){
C[i][j]=C[i-1][j-1]+C[i-1][j];
}
//C[i][i]=1;
}
}
int main(void){
int n,m;
Init();
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++){
//s[i][0]表示可以出现的种类数
scanf("%lld",&s[i][0]);
for(int j=1;j<=s[i][0];j++){
scanf("%lld",&s[i][j]);
}
}
_clr(dp,0);
//dp[i]表示字符串长度为i的情况数
//先枚举第一个字符的情况
for(int i=1;i<=s[1][0];i++){
if(s[1][i]<=m){
dp[s[1][i]]=C[m][s[1][i]];
}
}
//从第二个字符开始递推
for(int i=2;i<=n;i++){
if(s[i][0]){
for(int j=m;j>=0;j--){
//从计算方面看,dp[j]为0时后面计算没有意义
//从递推方面看,
if(dp[j]){
for(int k=1;k<=s[i][0] && j+s[i][k]<=m;k++){
if(s[i][k]){
//dp[j]是已经组成的j个字符的字符串,再加上s[i][k]个字符,有C[m-j][s[i][k]]中情况
dp[j+s[i][k]]+=dp[j]*C[m-j][s[i][k]];
}
}
}
}
}
}
printf("%lld\n",dp[m]);
}
return 0;
}