SRM459 Div1 Medium(500) NumberPyramids

NumberPyramids

下段が全部1でも頂上は2^baseLength-1なので、baseLengthは1000000以下と書いてあるけど、そんなに大きくはならない。
下段を決めればピラミッドが一意に定まる。下段をx[0], x[1], ……, x[baseLength-1]、c[i] = Comb(baseLength-1,i)とすると、頂上の値はΣc[i]x[i]。パスカルの三角形みたいな感じ。なので、この問題はΣc[i]x[i] = topを満たす解の個数となる。あとは動的計画法。v[i][j]を

を満たす解の個数とすると、v[i][j] = v[i][j-c[i] ] + v[i-1][j-c[i] ]。
例えば、x+3y+3z=15を満たす解の個数はx+3y+3z=12を満たす解の個数とx+3y=12を満たす解の個数の和。z>=2の場合が前者、z=1の場合が後者。

#include <vector>

using namespace std;

class NumberPyramids
{
public:
    int count( int baseLength, int top );
};

int NumberPyramids::count( int baseLength, int top )
{
    if ( baseLength >= 21 )
        return 0;

    //  v[j]：Σ[t=0,i] c[t] x[t] = j を満たす式の個数
    vector<int> v( top + 1, 1 );

    for ( int i=1; i<baseLength; i++ )
    {
        //  Comb( baseLength-1, i )
        long long c = 1;
        for ( int j=0; j<i; j++ )
            c *= baseLength-1 - j;
        for ( int j=1; j<=i; j++ )
            c /= j;

        vector<int> t = v;

        for ( int j=1; j<=top; j++ )
            if ( j - c >= 1 )
                v[j] = ( v[j-c] + t[j-c] ) % 1000000009;
            else
                v[j] = 0;
    }

    return v[top];

}