SRM 585 Div1 500 LISNumber

2013-07-20

16:00 |

数字 i が CS[i] 個あるとき、それらを並び替えて最長部分増加列の個数が K 個になるようにしたい。何通りあるか求める問題。
1≦N≦36, 1≦CS[i]≦36, 1≦K≦1296

dp[n][k] ... CS[i], i in [0, n) を使って k 個の LIS を作る方法の個数と置くのだろう
更新は dp[n][k] = Σ(pk in [0, k]) dp[n-1][pk] * (LISの個数がpk個からk個になるようなnの挿入箇所が何通りあるか)
dp[N][K] が答え

どんなときに LIS の個数が増えるか？
各 LIS の最後に n を置くと、LIS の個数は増えない（n-1までの数字しか置いてないので）。こういう場所は pk 個ある。
新しく置く CS[n] 個の n のうち、CS[n]-(k-pk) 個はこれらの場所から選んで 1 コずつおけばいい。
なので Comb(pk, CS[n]-(k-pk)) 通り

それ以外の場所に複数個 n を挿入すると、LIS の個数は置いただけ増える. その中から k-pk 個重複ありで置く。
Homogeneous Product(いままで置いた数字の数+1 - pk, k-pk)
Homogeneous Product(N, K) == Combination(N+K-1, K) ... 区切りを置くと考えるやつ
としたがサンプル合わず→おわり

(あとで)

LIS の個数が増えないとこに置いたら、以降その場所は LIS の個数が増える場所に変わるのであった
0 0 0 (LIS 3コ)
0 0 0 1 (LIS 3コ)
0 0 0 1 1 (LIS 4コ)

ということで LIS の個数が増えないとこに実際に置く数分だけ LIS の個数が増える場所を増やして
Homogeneous Product(いままで置いた数字の数+1 - (pk-(CS[n]-(k-pk))), k-pk)
としたら通った。

accepted in practice

#define MOD 1000000007LL
#define N_MAX 1300
#define K_MAX 1300
int comb[N_MAX][K_MAX];
ll combf(int n, int k) {
	if(!(0<=n && n<N_MAX)) return 0;
	if(!(0<=k && k<K_MAX)) return 0;
	return comb[n][k];
}

class LISNumber {
	public:
	int count(vector <int> CS, int K) {
		REP(n, N_MAX) comb[n][0] = 1;
		RANGE(n, 1, N_MAX) RANGE(m, 1, K_MAX) comb[n][m] = ((ll)comb[n-1][m-1] + comb[n-1][m]) % MOD;
		
		int N=CS.size();
		VVI dp(N+1, VI(K+1)); // dp[n][k] ... CS[i], i in [0, n) を使って k 個の LIS を作る方法の個数 % MOD
		dp[0][0] = 1;
		ll sum = 1;
		RANGE(i, 1, N+1) {
			RANGE(k, 1, K+1) {
				RANGE(pk, 0, k+1) {
					int add = k-pk; // in [0, k]
					int rest = CS[i-1] - add;
					ll plus = dp[i-1][pk] * combf(sum-(pk-rest)-1+add, add) % MOD * combf(pk, rest) % MOD;
					dp[i][k] += plus;
					dp[i][k] %= MOD;
				}
			}
			sum += CS[i-1];
		}
		return dp[N][K];
	}
};