学校资源网站建设,源码出售网站怎么做,3d建模用什么软件,建设厅网站174号文C1. 组队活动 SmallTime Limit: 1000msMemory Limit: 131072KB64-bit integer IO format: %lld Java class name: MainSubmit Status PID: 51280BNU ACM校队一共有名队员#xff0c;从到标号#xff0c;现在名队员要组成若干支队伍来相互学习、共同进步#xff0c;为了… C1. 组队活动 SmallTime Limit: 1000msMemory Limit: 131072KB64-bit integer IO format: %lld Java class name: MainSubmit Status PID: 51280BNU ACM校队一共有名队员从到标号现在名队员要组成若干支队伍来相互学习、共同进步为了保证学习效率每支队伍至多有名队员你需要计算出一共有多少种不同的组队方案。两个组队方案被视为不同的当且仅当存在至少一名队员在两种方案中有不同的队友。Input第一行是一个正整数表示测试数据的组数对于每组测试数据输入只有一行包含两个整数、。Output对于每组测试数据输出一行包含一个整数表示不同的组队方案的个数由于方案数可能很大请对取模后输出。Sample Input2 5 220 3Sample Output26 721625882思路dp。动态转移方程dp[i](dp[i](C[i-1][j]*dp[i-1-j])%E)%E;其中C为组合数用杨辉三角法可以求得。考虑当新加入的人有多少种组队法也就是和前面的人的组合按照不超过m名队员枚举所以从前面选出的人就是C[i-1][j],前i-1个人中选j个的选法然后前i-1剩下的按合理排的方案就为dp[i-1-j].所以两个相乘。 1 #includestdio.h 2 #includealgorithm 3 #includeiostream 4 #includestring.h 5 #includestdlib.h 6 #includequeue 7 #includestack 8 #includecstdio 9 #define sc(x) scanf(%I64d,x)10 #define pr(x) printf(%I64d,x)11 #define prr(x) printf(%I64d\n,x);12 #define prrr(x) printf(%I64d ,x);13 const long long E998244353;14 using namespace std;15 long long C[1005][1005];16 long long dp[1005];17 void run()18 {19 int i,j;20 for(i0; i1000; i)21 for(j0; ji; j)22 if(j0||ij)23 C[i][j]1;24 else25 C[i][j](C[i-1][j-1]C[i-1][j])%E;26 }//杨晖三角27 int main(void)28 {29 run();30 int i,j,k,p,q;31 scanf(%d,k);32 while(k--)33 {34 memset(dp,0,sizeof(dp));35 scanf(%d %d,p,q);36 dp[0]1;37 dp[1]1;38 for(i2; ip; i)39 {40 for(j0; jq; j)//枚举种类41 {42 if(i-1-j0)43 {44 break;45 }46 else47 {48 dp[i](dp[i](C[i-1][j]*dp[i-1-j])%E)%E;49 }50 }51 }52 printf(%lld\n,dp[p]);53 }54 return 0;55 } 转载于:https://www.cnblogs.com/zzuli2sjy/p/5181122.html
