首页 > 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. 斑的时空忍术来源 斑自己都承认 他的瞳力在与初代战斗后就一直没有恢复 而且现在出场的写轮眼使用者 除了卡卡西的空间撕裂 似乎多与精神类 灵魂类攻击(幻术)有关 还有少量如天照 须佐一样的特殊物理攻击 与空间的联系并不大 硬说斑的时空忍术来源于写轮眼 有些

  2. 斑的时空忍术来源 斑自己都承认 他的瞳力在与初代战斗后就一直没有恢复 而且现在出场的写轮眼使用者 除了卡卡西的空间撕裂 似乎多与精神类 灵魂类攻击(幻术)有关 还有少量如天照 须佐一样的特殊物理攻击 与空间的联系并不大 硬说斑的时空忍术来源于写轮眼 有些

  3. 斑的时空忍术来源 斑自己都承认 他的瞳力在与初代战斗后就一直没有恢复 而且现在出场的写轮眼使用者 除了卡卡西的空间撕裂 似乎多与精神类 灵魂类攻击(幻术)有关 还有少量如天照 须佐一样的特殊物理攻击 与空间的联系并不大 硬说斑的时空忍术来源于写轮眼 有些

  4. 斑的时空忍术来源 斑自己都承认 他的瞳力在与初代战斗后就一直没有恢复 而且现在出场的写轮眼使用者 除了卡卡西的空间撕裂 似乎多与精神类 灵魂类攻击(幻术)有关 还有少量如天照 须佐一样的特殊物理攻击 与空间的联系并不大 硬说斑的时空忍术来源于写轮眼 有些

  5. 斑的时空忍术来源 斑自己都承认 他的瞳力在与初代战斗后就一直没有恢复 而且现在出场的写轮眼使用者 除了卡卡西的空间撕裂 似乎多与精神类 灵魂类攻击(幻术)有关 还有少量如天照 须佐一样的特殊物理攻击 与空间的联系并不大 硬说斑的时空忍术来源于写轮眼 有些

  6. 斑的时空忍术来源 斑自己都承认 他的瞳力在与初代战斗后就一直没有恢复 而且现在出场的写轮眼使用者 除了卡卡西的空间撕裂 似乎多与精神类 灵魂类攻击(幻术)有关 还有少量如天照 须佐一样的特殊物理攻击 与空间的联系并不大 硬说斑的时空忍术来源于写轮眼 有些

  7. 斑的时空忍术来源 斑自己都承认 他的瞳力在与初代战斗后就一直没有恢复 而且现在出场的写轮眼使用者 除了卡卡西的空间撕裂 似乎多与精神类 灵魂类攻击(幻术)有关 还有少量如天照 须佐一样的特殊物理攻击 与空间的联系并不大 硬说斑的时空忍术来源于写轮眼 有些

  8. 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

  9. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    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)