UpDownNess [SRM 694 : Div2 Hard] - はまやんはまやんはまやん

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14304

1～Nの数が1つずつある順列を考える。
その順列に対して、「lo-hi-lo triple（以下LHL）」の個数を数える。

lo-hi-lo triple（LHL）
順列Pの i < j < k に対して P[i] < P[j] > P[k] である3つの組

というLHLがあるので、個数は3つ

1～Nの数が1つずつある順列は全部でN!個あるが、その中でLHLの個数がK個である数列の個数を数えよ

1 <= N <= 50
0 <= K <= 5000

考察

1. まず、数学的に解けないか考えてみる
2. うーむ。無理そう。組合せといえばDPかな？
3. DPでいけないかな…
4. Nの制限が小さいけど、区間DPとか最大最小を添え字にするとかかな…
5. どれも無理そうだったので、実験して考えてみる

頑張って実験してみる

6. DPで大切なのは「状態をまとめること」
7. 数と場所を決定していくのをうまい具合に調整すると、状態がまとめられて嬉しい
8. この方針で実験して、考えて…

9. 数の小さい順から決定していくと、挿入した所の左側は必ず小さく、右側も必ず小さくなる

1,2,3,4を挿入しながら順列を決定していくとする。

1
↓ + 2
1 2, 2 1
この2つはどこに3を入れても、増えるLHLの数は変わらないから同一視できる！！
↓ + 3
3 1 2, 1 3 2, 1 2 3, 3 2 1, 2 3 1, 2 1 3
これらもどこに3を入れても、増えるLHLの数は変わらないから同一視できる！！
だが、増えるLHLの数は変わらないが、「今までのLHLの数は違う場合がある」ので別の場合として分ける

10. dp[何番目の数まで決定して][LHLの数が現時点で何個で] = 場合の数
を更新していけば解ける

実装

typedef long long ll;
#define MOD 1000000007

ll dp[55][10050];
class UpDownNess {
public:
	int count(int N, int K)
	{
		dp[0][0] = 1;
		rep(i, 1, N+1) rep(j, 0, K + 1) {
			rep(k, 0, i) {
				int left = k;
				int right = i - 1 - left;
				dp[i][j + left * right] += dp[i - 1][j];
				dp[i][j + left * right] %= MOD;
			}
		}
		return dp[N][K] % MOD;
	}
};