一页书的书
时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 53 测试通过 : 10
总提交 : 53 测试通过 : 10
题目描述
一页书前辈作为一位得道高僧，在他无悔的生涯中创作了许多经典，被世人称作百世经纶。这一天有m个粉丝来膜拜书大，书大很开心，决定送他们每人一本经典。已知一页书一共创作了n部作品，每部作品分别有a1、a2…an份藏本，那么书大一共可以有多少种送书的选择呢？（由于计算结果可能很大，请把结果对1000000007取模）
输入
第一行是一个正整数T表示有T组数据
每组数据第一行是两个正整数n,m(n,m<=20)
第二行是n个正整数ai(ai<=20)
输出
一个正整数k表示方法的总数对1000000007（10^9+7）取模的结果
样例输入
2
2 3
2 2
2 3
3 3
样例输出
6
8
题目来源
LY:D
题解：
剧透的田神！！！！！！！ dp+组合数。
dp[i][j]表示前i个人用了j种书
dp[i][j+1] = sigma ( c(i,x) * dp[i - x][j] )
|
Accepted
|
0MS
|
216K
|
1443Byte
|
2015-03-28 16:57:56.0
|
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <queue> #define ll long long
int const N = ;
int const M = ;
int const inf = ;
ll const mod = ; using namespace std; int n,m;
int a[N];
ll dp[N][N];
ll c[N][N];
int T; void ini1()
{
memset(c,,sizeof(c));
int i,j;
for(i=;i<=;i++){
c[i][]=;
}
for(i=;i<=;i++){
for(j=;j<=;j++){
c[i][j] = (c[i-][j-]+c[i-][j])%mod;
}
}
/*
for(i=1;i<=10;i++){
for(j=0;j<=i;j++){
printf(" i=%d j=%d c=%I64d\n",i,j,c[i][j]);
}
}*/
} void ini()
{
scanf("%d%d",&n,&m);
memset(dp,,sizeof(dp));
int i;
for(i=;i<=n;i++){
scanf("%d",&a[i]);
}
dp[][]=;
} void solve()
{
int i,j,k;
for(j=;j<=n;j++){
for(i=;i<=m;i++){
for(k=;k<=min(a[j],i);k++){
dp[i][j] = (dp[i][j] + c[i][k] * dp[i-k][j-]) %mod;
}
}
}
} void out()
{
printf("%I64d\n",dp[m][n]);
} int main()
{
ini1();
//freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%d",&T);
for(int cnt=;cnt<=T;cnt++)
//while(T--)
//while(scanf("%d%d",&n,&m)!=EOF)
{
ini();
solve();
out();
}
}