题面
给定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\n",i,f[n]);
- }
【UVA12034】比赛名次
原文：https://www.cnblogs.com/NSD-email0820/p/9879004.html
