---恢复内容开始---
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
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
2
2
3
Sample Output
3
13
代码如下:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> #define ll long long using namespace std; const int N = ;
const int MOD = ;
ll dp[N][N], ans[N], fac[N]; void init()
{
fac[] = ;
for(int i = ; i < N; i++)
fac[i] = (fac[i-]*i)%MOD; //阶乘初始化
memset(dp, , sizeof(dp));
for(int n = ; n < N; n++)
{
dp[n][] = ;
dp[n][n] = ;
for(int k = ; k < n; k++)
{
dp[n][k] = dp[n-][k-]+k*dp[n-][k];
dp[n][k] %= MOD;
}
}
} int main()
{
int T, n;
init();
cin>>T;
while(T--)
{
cin>>n;
ll ans = ;
for(int i = ; i <= n; i++)
ans = (ans + fac[i]*dp[n][i]) % MOD;
cout<<ans<<endl;
} return ;
}