Examining the Rooms - 第一类斯特灵数-白红宇

Examining the Rooms - 第一类斯特灵数

阅读量：5365 次

发布时间：2019-06-15

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

---恢复内容开始---

2017-08-10 20:32:37

writer：pprp

题意如下：

Recently in Teddy's hometown there is a competition named "Cow Year Blow Cow".N competitors had took part in this competition.The competition was so intense that the rank was changing and changing.

Now the question is:

How many different ways that n competitors can rank in a competition, allowing for the possibility of ties.

as the answer will be very large,you can just output the answer MOD 20090126.

Here are the ways when N = 2:

P1 < P2

P2 < P1

P1 = P2

InputThe first line will contain a T,then T cases followed.

each case only contain one integer N (N <= 100),indicating the number of people.OutputOne integer pey line represent the answer MOD 20090126.Sample Input

Sample Output

代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define ll long longusing namespace std;const int N = 110;const int MOD = 20090126;ll dp[N][N], ans[N], fac[N];void init(){    fac[1] = 1;    for(int i = 2; i < N; i++)        fac[i] = (fac[i-1]*i)%MOD;   //阶乘初始化    memset(dp, 0, sizeof(dp));    for(int n = 1; n < N; n++)    {        dp[n][1] = 1;        dp[n][n] = 1;        for(int k = 2; k < n; k++)        {            dp[n][k] = dp[n-1][k-1]+k*dp[n-1][k];            dp[n][k] %= MOD;        }    }}int main(){    int T, n;    init();    cin>>T;    while(T--)    {        cin>>n;        ll ans = 0;        for(int i = 1; i <= n; i++)            ans = (ans + fac[i]*dp[n][i]) % MOD;        cout<
         
          <

转载于:https://www.cnblogs.com/pprp/p/7341393.html

你可能感兴趣的文章