The mook joong（法則を探します+数学の“仕切り”の思想を組み合わせます）

リンク:http://acm.hdu.edu.cn/showproblem.php?pid=5366
The mook jun
Time Limit：2000/1000 MS（Java/Others）    メモリLimit：65536/65536 K（Java/Others）Total Submission（s）：45    Acceepted Submission(s)：31
Problem Description
！[](././/data/imags/C 613-001-1.jpg)
ZJiaQ want to become a strong man、so he decided to player the mook jun。ZJiaQ want to put some mook jogs in his backyard.His backyard consist of n briks that is 1*1,so it is 1*n。ZJiaQ want to put a mooking in a brick.because of the hands of the mook jun，the distance of two mook jougs shougs shougs 2 bricks.Now JiaQ want to know howmanways can Zialmollokone。
 
Input
The re ar multiplly cases.For each case，there is a single integer n(1==n==60)
 
Output
Print the ways in a single line for each case.
 
Sample Input

 
   

     1 2 3 4 5 6 
   
 
  

对应中文题意（来自BC）：

ZJiaQ      ，           。ZJiaQ              1*1      1*n    。  ZJiaQ     ，                   ，         ，                   ，  ZJiaQ                 ，      。

説明を入力

       ，            n(1 < = n < = 60)

出力の説明

入力サンプル

1	
2
3
4
5
6

出力サンプル

1
2
3
5
8
12

プログラミング思想:
2つの杭の間のタイルは2つ以上でなければならないので、2つの杭を押し出す時には少なくとも4つのタイルが必要です。3つの木人杭は少なくとも7つのタイルが必要です。4つの木人杭は少なくとも10枚のタイルが必要です。だから、nブロックとn>=4がある時に、並べられる木人杭の数は最大2+(n-4)/3まで数え上げて、1つの木人を並べます。/3つの木杭の配置方案数は、一つ一つの列挙の状況を計算する時、ここで数学を組み合わせた知識を使いました。2つの木杭を並べる時、2つの木杭の間の床れんがは2つ以上でなければいけません。つまり、2つの木の杭の間の隙間は少なくとも2つです。だから、n-2つの床れんがある位置はこの2つの木杭を置くことが選択できます。ここでは数学の組み合わせを採用します。「仕切り」の思想は、まずn-2個の床れんがに対して、二つの位置を選んで、木人杭を置いて、それからこの二つの木人杭の中間に更に2枚の地れんがを追加して、二つの木人杭の間の地れんがを満たすのは2つの条件より大きくなければなりません。ここに添付したこの2つの地れんがと、元来た2つの木人の杭の間の地ならぶの間のタイルは同じです。したがって、nブロックブロックのタイルがあり、n>=4の場合、2つの木人杭に対応する最大の配列数はCn 2であり、同じ理屈で、3つの木人杭がある場合、仕切りの大きさは少なくとも2*2=4で、木人杭を置く位置を選択した後、木人杭の2つの間に大きさを2つの「仕切り」とすることで、nブロックのタイルがある。（n-4）3です。だから、n>=4の場合、m=2+(n-4)/3の場合、全体の配置数は以下の通りです。
C（n）1＋C（n−2）2＋C（n−4）3＋…C（n−1）＊2）m
ACコード:

#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define MAXN 1000100
using namespace std;
LL n,m,ans;
int a[4];
LL Cnm(LL n,LL m)//     C(n,m) 
{
    if(m>n/2)//      ，        
    m=n-m;
    LL a=1,b=1;
    for(int i=1;i<=m;i++)//    m    
    {
        a*=n+1-i;//   i        a    b 
        b*=i;
        if(a%b==0)
        {
            a/=b;
            b=1;
        }
    }
    return a/b;
}

int main()
{
    
    int i,j;
    a[1]=1;
    a[2]=2;
    a[3]=3;
    while(scanf("%I64d",&n)!=EOF)
    {
        if(n<=3)
            printf("%d
",a[n]);
        else
        {
            m=2+(n-4)/3;
            ans=0;
            for(i=1;i<=m;i++)
            {
                ans+=Cnm(n-(i-1)*2,i);
            }
            printf("%I64d
",ans);
        }    
    }
}