首页 > 代码库 > UVa 12034 比赛名次（递推）
UVa 12034 比赛名次（递推）
https://vjudge.net/problem/UVA-12034
题意：
A、B两人赛马，最终名次有3种可能：并列第一；A第一B第二；B第一A第二。输入n，求n人赛马时最终名次的可能性的个数除以10056的余数。
思路：
设答案为f(n),假设第一名有i个人，接下来就会有f(n-i)种可能性，所以答案为
。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<queue> 6 using namespace std; 7 8 const int maxn=1000+100; 9 #define mod 1005610 11 int c[maxn][maxn];12 int f[maxn];13 14 void init()15 {16 for(int i=0;i<maxn;i++)17 {18 c[i][0]=1;19 for(int j=1;j<=i;j++)20 {21 c[i][j]=c[i-1][j-1]+c[i-1][j];22 c[i][j]%=mod;23 }24 }25 }26 27 int solve(int n)28 {29 if(f[n]) return f[n];30 for(int i=1;i<=n;i++)31 {32 f[n]+=c[n][i]*solve(n-i);33 f[n]%=mod;34 }35 return f[n];36 }37 38 int main()39 {40 int T;41 scanf("%d",&T);42 init();43 f[0]=1;44 for(int kase=1;kase<=T;kase++)45 {46 int n;47 scanf("%d",&n);48 solve(n);49 printf("Case %d: %d\n",kase,f[n]);50 }51 }
UVa 12034 比赛名次（递推）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。