有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;
}