首页 > ACM题库 > HDU-杭电 > HDU 2811-Deputy General-数学[解题报告]HOJ
2014
02-17

HDU 2811-Deputy General-数学[解题报告]HOJ

Deputy General

问题描述 :

War is cruel .Every one has a boss except LvBu. LvBu want to rally the troops to make his army stronger .
The rule is: everyone may have 0~2 deputy generals and must have only one boss(except LvBu).Everyone has his own level(all levels are different),and his deputy generals’ level must less than his. You can assume no one is more levelful than LvBu.
For example , LvBu’s level is 4,ChenGong’s level is 3,ZhangLiao’s level is 2 and GaoShun’s level is 1.So,We can make five way :

Now ,give you the number of generals in LvBu’s army.Please tell me the number of possible methods?
The answer might be very large. Output your answers mod k.

输入:

Each line contains two integers n and k, indicating the number of LvBu’s generals (including LvBu).
1<= n <= 1000;2<=k<=1,000,000,000

输出:

Each line contains two integers n and k, indicating the number of LvBu’s generals (including LvBu).
1<= n <= 1000;2<=k<=1,000,000,000

样例输入:

1 10007
2 10007
3 10007
4 10007

样例输出:

1
1
2
5


设g[i]表示i个人构成的种数。
c[i][j]表示组合数C(i,j);
g[i]=sum{g[k]*f[i-2][k-1]*g[i-k-1])}(1<=k 公式不懂啊。。。。。。。
注意:取模的时候会溢出。
还有个类似的:
1 + x + x^2 + 2*x^3 + 5*x^4 + 16*x^5 + 61*x^6 + 272*x^7 + 1385*x^8 + …
给出n个字母使它们的排序满足”<",">“,”<",">“…交替出现的关系:
Sequence starts 1,1,2,5,16,… since possibilities are
{}, {A}, {AB}, {ACB, BCA}, {ACBD, ADBC, BCAD, BDAC, CDAB},
{ACBED, ADBEC, ADCEB, AEBDC, AECDB, BCAED, BDAEC, BDCEA,
BEADC, BECDA, CDAEB, CDBEA, CEADB, CEBDA, DEACB, DEBCA},
etc. – Henry

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define O 1005
#define Int __int64
using namespace std;
Int f[O][O];
Int g[O];
Int n,k;
int main()
{
    int i,j;
    while(scanf("%I64d%I64d",&n,&k)!=EOF)
    {
        for(i=1;i<=n;i++)
        {   
            f[i][0]=f[i][i]=1;
            for(j=1;j<i;j++)
            f[i][j]=(f[i-1][j-1]+f[i-1][j])%k;
        }
       g[0]=1,g[1]=1,g[2]=1;
        for(i=3;i<=n;i++)
        {   
            g[i]=0;
            for(j=1;j<i;j++)
               g[i]=(g[i]+g[j]*f[i-2][j-1]%k*g[i-j-1]%k)%k;
        }
        printf("%I64d\n",g[n]%k);
    }
    return 0;
}

 


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  3. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环