noj 2033 一页书的书 [ dp + 组合数 ]-白红宇

noj 2033 一页书的书 [ dp + 组合数 ]

阅读量：6457 次

发布时间：2019-06-23

本文共 1893 字，大约阅读时间需要 6 分钟。

一页书的书

时间限制(普通/Java) :

1000 MS/

3000 MS

运行内存限制 : 65536 KByte

总提交 : 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 3

2 2

2 3

3 3

样例输出

题目来源

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

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
          6 #include 
          
            7 #include 
           
             8 9 #define ll long long10 int const N = 25;11 int const M = 205;12 int const inf = 1000000000;13 ll const mod = 1000000007;14 15 using namespace std;16 17 int n,m;18 int a[N];19 ll dp[N][N];20 ll c[N][N];21 int T;22 23 void ini1()24 {25 memset(c,0,sizeof(c));26 int i,j;27 for(i=0;i<=30;i++){28 c[i][0]=1;29 }30 for(i=1;i<=30;i++){31 for(j=1;j<=30;j++){32 c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod;33 }34 }35 /*36 for(i=1;i<=10;i++){37 for(j=0;j<=i;j++){38 printf(" i=%d j=%d c=%I64d\n",i,j,c[i][j]);39 }40 }*/41 }42 43 void ini()44 {45 scanf("%d%d",&n,&m);46 memset(dp,0,sizeof(dp));47 int i;48 for(i=1;i<=n;i++){49 scanf("%d",&a[i]);50 }51 dp[0][0]=1;52 }53 54 void solve()55 {56 int i,j,k;57 for(j=1;j<=n;j++){58 for(i=0;i<=m;i++){59 for(k=0;k<=min(a[j],i);k++){60 dp[i][j] = (dp[i][j] + c[i][k] * dp[i-k][j-1]) %mod;61 }62 }63 }64 }65 66 void out()67 {68 printf("%I64d\n",dp[m][n]);69 }70 71 int main()72 {73 ini1();74 //freopen("data.in","r",stdin);75 // freopen("data.out","w",stdout);76 scanf("%d",&T);77 for(int cnt=1;cnt<=T;cnt++)78 //while(T--)79 //while(scanf("%d%d",&n,&m)!=EOF)80 {81 ini();82 solve();83 out();84 }85 }

转载于:https://www.cnblogs.com/njczy2010/p/4374467.html

你可能感兴趣的文章