SRM585 Div1 Medium "LISNumber"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12419
訳
A を整数のシーケンスとする。我々はいくつかの(1以上の)増加列の連結したものとして、シーケンスを作成したい。AのLISNumberとは増加列の最小の数のことである。
例えば、A = {1, 4, 4, 2, 6, 3}のLISNumberは4である。なぜならAは{1, 4} + {4} + {2, 6} + {3}として、4つの増加列を連結して作成できるが、3つの(またはそれより少ない)増加列を連結してAを作成する事はできないからである。
他の例として、B = {10, 20, 30}のLISNumberは1である。なぜならBはすでに増加列だからである。
あなたは0~N-1の数字が書かれたカードを持っている。数字iのカードはcardsnum[i]枚だけ持っている。
あなたにはint[] cardsnumと、int Kが与えられる。あなたは、LISNumberがKとなるように、全てのカードを1列に配置したい。あなたは全てのカードを使わなければならないが、それを好きな順番で並べる事が出来る。
カードの並べ方のパターン数を返せ。ただし、同じ種類のカードは区別がつかないものとする。
制約
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が1増えるだけのカードの置き方は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; } }