SRM585 Div1 Medium "LISNumber"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12419

訳

A を整数のシーケンスとする。我々はいくつかの（１以上の）増加列の連結したものとして、シーケンスを作成したい。AのLISNumberとは増加列の最小の数のことである。

例えば、A = {1, 4, 4, 2, 6, 3}のLISNumberは4である。なぜならAは{1, 4} + {4} + {2, 6} + {3}として、４つの増加列を連結して作成できるが、３つの（またはそれより少ない）増加列を連結してAを作成する事はできないからである。

他の例として、B = {10, 20, 30}のLISNumberは1である。なぜならBはすでに増加列だからである。

あなたは0～N-1の数字が書かれたカードを持っている。数字iのカードはcardsnum[i]枚だけ持っている。

あなたにはint[] cardsnumと、int Kが与えられる。あなたは、LISNumberがKとなるように、全てのカードを１列に配置したい。あなたは全てのカードを使わなければならないが、それを好きな順番で並べる事が出来る。

カードの並べ方のパターン数を返せ。ただし、同じ種類のカードは区別がつかないものとする。

制約

1 <= N <= 36
1 <= cardsnum[i] <= 36
1 <= K <= 1296

考えた事

カードを小さい数字順に置いていくとする。

現在のカードの並びの状態について、カードの枚数がc、今置こうとしているカードの数字がi、同じ数字のカードの枚数がj、LISNumberがkとする。

最後の数字がiの増加列はj個だけあるので、LISNumberが増えないようなカードの置き方の数not_incはk - jとなる（ただし、k < jであれば0）。

LISNumberが１増えるだけのカードの置き方はc + 1 - not_incとなる。

よって、dp[カードの種類][同じ種類のカードの置いた数][LISNumber]として、DPを更新していく。

同じ種類のカードを区別しないので、最終的にcardsnum[i]! ( 0 <= i < N )で割ればよい。

ソースコード

const int MOD = 1000000007;

long long F[40];
long long dp[40][40][1300];

class LISNumber {
public:

    void initF(){
        F[0] = F[1] = 1;
        for( int i = 2; i < 40; i++ ){
            F[i] = F[i-1] * i % MOD;
        }
    }

    long long mod_pow( long long a, long long b ){
        long long r = 1;
        while( b > 0 ){
            if( b & 1 ) r = r * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return r;
    }

    long long mod_inv( long long a ){
        return mod_pow( a, MOD - 2 );
    }

    void add( long long& target, long long a ){
        target = (target + a) % MOD;
    }

    int count(vector <int> cardsnum, int K){

        int N = cardsnum.size();

        memset( dp, 0, sizeof(dp) );
        dp[0][0][0] = 1;

        int c = 0; // 置いたカードの総数

        for( int i = 0; i < N; i++ ){
            int M = cardsnum[i];
            for( int j = 0; j < M; j++ ){
                for( int k = 0; k <= K; k++ ){
                    // LISNumberが増えないような置き方の数
                    int nic = max( 0, k - j ); 
                    // LISNumberが増えるような置き方の数
                    int ic = c + 1 - nic;

                    // 最後だったら
                    if( j == M - 1 ){
                        // LISが増える場所に置く
                        add( dp[i+1][0][k+1], dp[i][j][k] * ic );
                        // LISが増えない場所に置く
                        add( dp[i+1][0][k], dp[i][j][k] * nic );
                    }else{
                        // LISが増える場所に置く
                        add( dp[i][j+1][k+1], dp[i][j][k] * ic );
                        // LISが増えない場所に置く
                        add( dp[i][j+1][k], dp[i][j][k] * nic );
                    }
                }
                c++;
            }
        }

        // カードを区別しないので、cardsnum[i]!で割っていく
        initF();
        long long ans = dp[N][0][K];
        for( int i = 0; i < N; i++ ){
            ans = ans * mod_inv( F[cardsnum[i]] ) % MOD;
        }

        return (int)ans;
    }
}