【UVA12034】比赛名次

题面

给定n匹马，要求出可能的排名情况（可能并列）

n<=1000，答案对10056取模

分析

和我以前的数论三题里面的一道题一样，但是那个题没有取模，于是n只在10以内

设f(n)为答案 则第一名可能是1~n-1个，第一名一个的时候就是C（n,1）*f(n-1)，第一名两个的时候就是C（n,2）*f(n-2)

因此可得到 f(n)=∑C(n,i)*f(n-i)

代码

#include<bits/stdc++.h>  
using namespace std;  
#define N 1010  
#define mod 10056  
int t,n,f[N],c[N][N];  
inline void pre()  
{  
    c[0][0]=c[1][0]=1;  
    for(int i=1;i<N;i++)  
    {  
        c[i][0]=1;  
        for(int j=1;j<=i;j++)  
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;  
    }  
    for(int i=1;i<N;i++)  
    {  
        f[i]=1;  
        for(int j=1;j<=i;j++)  
            f[i]+=f[i-j]*c[i][j],f[i]%=mod;  
    }  
}  
  
int main()  
{  
    cin>>t;pre();  
    for(int i=1;i<=t;i++)  
        cin>>n,printf("Case %d: %d
",i,f[n]);  
}