2014
02-12

# 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;
}

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)