首页 > ACM题库 > HDU-杭电 > hdu 2643 Rank[解题报告]C++
2014
02-12

hdu 2643 Rank[解题报告]C++

Rank

问题描述 :

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

输入:

The first line will contain a T,then T cases followed.
each case only contain one integer N (N <= 100),indicating the number of people.

输出:

The first line will contain a T,then T cases followed.
each case only contain one integer N (N <= 100),indicating the number of people.

样例输入:

2
2
3

样例输出:

3
13

题目要求算出大小关系的所有情况,我们把相等的放在一起,他们之间没有大小关系,形成分组,这个就是由第二类斯特灵数算出来的,在对分好的组进行全排列。

#include<stdio.h>
 typedef long long i64;
 int main()
 {
     int T,n;
     i64 s[150][150],f[150];
     scanf("%d",&T);
     f[0]=1;
     for(int i=1;i<=100;i++)
     {
         s[i][i]=1;s[i][1]=1;f[i]=f[i-1]*i%20090126;
     }
     for(int i=2;i<=100;i++)
     for(int j=2;j<=i;j++)
     s[i][j]=(s[i-1][j-1]+j*s[i-1][j])%20090126;
     while(T--)
     {
         i64 sum=0;
         scanf("%d",&n);
         for(int i=1;i<=n;i++)
         sum+=f[i]*s[n][i]%20090126;
         printf("%d\n",sum%20090126);
     }
     return 0;
 }

 

解题转自:http://www.cnblogs.com/Acgsws/archive/2013/07/19/3201150.html


  1. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)