hdu 1028 Ignatius and the Princess III(整数分割が大きいデータ量テンプレート)

タイトルリンク:
クリックしてリンクを開く
テーマ:
整数を分割して、順序の異なっている情況だけを並べて1種を計算して、最後に全部で何種類の情況があることを聞きます
テーマ分析:
テンプレート問題

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 127

using namespace std;

typedef long long LL;
LL p[MAX];

void perpare ( )
{
    LL i , j , k , s , o;
    p[0] = 1;
    for ( i = 1 ; i < MAX ; i++  )
    {
        j = 1 , k = 1 , s = 0 , o = -1;
        for ( ; j > 0 ; k++ , o *= -1 )
        {
            j = i - ( 3*k*k+k)/2;
            if ( j >= 0 )  s-= o * p[j];
            j = i - ( 3*k*k-k)/2;
            if ( j >= 0 ) s -= o* p[j];
        }
        p[i] = s;
    }
}

int main ( )
{
    perpare();
    /*for ( int i = 0 ; i <= 10 ; i++ )
        printf ( "%d " , p[i] );
    cout << endl;*/
    int n;
    while ( ~scanf ( "%d" , &n ))
    {
        printf ( "%I64d
" , p[n] );
    }
}