首页 > 代码库 > Gym Gym 101147G 第二类斯特林数

Gym Gym 101147G 第二类斯特林数

2024-09-27 14:59:39   214人阅读

题目链接：http://codeforces.com/gym/101147/problem/G

题意：n个人，去参加k个游戏，k个游戏必须非空，有多少种放法?

分析： 第二类斯特林数，划分好k个集合后乘以阶乘； 

 

技术分享
 1 #include <bits/stdc++.h> 2  3 using namespace std; 4  5 const int maxn = 1010; 6 const long long MOD = 1000000000 + 7L; 7 long long stir[maxn][maxn]; 8 long long fac[maxn]; 9 10 void init() {11 12     fac[1] = fac[0] = 1;13     for(int i=2;i<=1000;i++) {14         fac[i] = fac[i-1]*i%MOD;15     }16 17 18     stir[1][1]=1;19     for(int i=2; i<=1000; i++)20         for(int j=1; j<=i; j++)21             stir[i][j]=(stir[i-1][j-1]+(long long)j*stir[i-1][j]%MOD)%MOD;22 }23 24 int main() {25     freopen("galactic.in","r",stdin);26     init();27     int t;28     scanf("%d",&t);29     while(t--) {30         int n,k;31         scanf("%d%d",&n,&k);32 33         if(n>=k) {34             printf("%I64d\n",stir[n][k]*fac[k]%MOD);35         }36         else puts("0");37 38     }39     return 0;40 }
View Code

 

Gym Gym 101147G 第二类斯特林数


联系
我们