本文共 844 字，大约阅读时间需要 2 分钟。

题目大意：

n匹马比赛，计算通过终点的可能情况的数量 （可以并列）

(结果对10056取模）

思路：

个人感觉这种题需要找到一种“继承”关系。

就比如这题：用 f[i] 表示有 i 匹马的，假如有n个马中，有一个马是第一的话，那么剩下的马组成的情况就是 f[n-1]， 进一步考虑，假设有m匹马第一，那剩下的就是 f[n-m] 。所以m匹马第一的总情况就是C_n^m *f[n-m]。

具体过程

有了上述思路就很简单了，求出组合数，然后进行递推。

代码：

#include
   
    #include
    
     #include
     
      using namespace std;const int mod=10056;int n,c[1001][1001],f[1001];int main(){
       scanf("%d",&n);    f[0]=f[1]=1;c[1][1]=c[1][0]=1;    for(int i=2;i<=1000;++i){
           c[i][0]=c[i][i]=1;        for(int j=1;j<=i;++j){
               c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;            f[i]=(f[i]+(f[i-j]*c[i][j])%mod)%mod;        }    }    for(int i=1;i<=n;++i){
           int x;        scanf("%d",&x);        printf("Case %d: %d\n",i,f[x]);    }    return 0;}
     
    
   

一些思考

比赛的时候，知道把一个大问题给分解成小问题，但是没有想到如何分解。

现在想想，要分的小情况一定要是之前求出结果的，否则会全部木大。

日常中二

就这一直努力下去吧！

转载地址：http://tuuci.baihongyu.com/