SRM484 Div1 Medium(550) PuyoPuyo

PuyoPuyo

例えばL=4のとき、長さnの全消しできるぷよの並びは、
○××○××○××○□□
と表せる。ただし、××と□□は長さ0以上n未満の全消しできるぷよの並びで、××は消している途中に○が底に付かない。長さと全消し中に底に付くぷよの色数ごとに全消しできる並びの数を記憶して動的計画法。L≦10なので○の中に×を挿入する方法はもう１段の動的計画法で求める。

#include <vector>

using namespace std;

class PuyoPuyo{public:
int theCount( int L, int N )
{
    if ( N % L > 0 )
        return 0;

    const int M   = 1000000007;
    const int d2  =  500000004;     //  1/2
    const int d4  =  250000002;     //  1/4
    
    int n = N / L;

    //  [i][j]　i*L個のぷよを使って全消しできる並びの数
    //  ただし、途中で底にj+1色のぷよが接する
    vector<vector<long long> > T( n+1, vector<long long>( 4 ) );

    T[1][0] = 4;

    for ( int i=2; i<=n; i++ )
    {
        //  [i]　i*L個のぷよをL個の同色のぷよの間に挟んで全消しができる並びの数
        vector<long long> S( i );
        S[0] = 1;
        for ( int j=1; j<=i-1; j++ )
            S[j] = ( 3*T[j][0] + 2*T[j][1] + T[j][2] ) * d4 % M;

        for ( int j=0; j<L-2; j++ )
        {
            vector<long long> P = S;
            S[0] = 1;
            for ( int k=1; k<=i-1; k++ )
            {
                S[k] = P[k];
                for ( int l=1; l<=k; l++ ) 
                    S[k] += P[k-l] * (3*T[l][0]+2*T[l][1]+T[l][2]) % M * d4,
                    S[k] %= M;
            }
        }

        for ( int j=0; j<i-1; j++ )
        {
            T[i][0] += S[j] * T[i-j-1][0] % M * d4 * 1;
            T[i][1] += S[j] * T[i-j-1][0] % M * d4 * 3;
            T[i][1] += S[j] * T[i-j-1][1] % M * d2 * 1;
            T[i][2] += S[j] * T[i-j-1][1] % M * d2 * 1;
            T[i][2] += S[j] * T[i-j-1][2] % M * d4 * 3;
            T[i][3] += S[j] * T[i-j-1][2] % M * d4 * 1;
            T[i][3] += S[j] * T[i-j-1][3] % M;
            T[i][0] %= M,  T[i][1] %= M,  T[i][2] %= M,  T[i][3] %= M;
        }
        T[i][0] = ( T[i][0] + S[i-1] ) % M;

        for ( int j=0; j<4; j++ )
            T[i][j] = T[i][j] * 4 % M;
    }

    return ( T[n][0] + T[n][1] + T[n][2] + T[n][3] ) % M;
}};

実はシンプルに解けるらしいorz