CF243E: Sereja and Sets

http://codeforces.com/contest/425/problem/E

ずっと前に解けなかった問題。ひさしぶりに見たらそんな難しくなかった。

余分における区間の特性を考えよう。
区間スケジューリング問題の要領で、区間のうちとれるものの中で右側の座標が一番小さいものをとっていく。
今新しく区間をとったとして、その右側の座標をx1,一つ前にとった区間の右側の座標をx2とする。
いまx1が取れるもののうち最小なので、右側の座標がx1より小さい区間はとることができない。
右側の座標がx1の区間は(x1-x2)個とれ、
右側の座標がx1より大きい区間は、x1 * (N - x1)個取れるが、左側が0<=x<=x2を満たす区間はすでにとってあるので、
結局ダブりを除くと(x1 - x2) * (N - x1)個とれる。あとは適応に2のべき乗を考えてdpする。

int N, K;
ll pow2[300010];
ll dp[510][510];

void solve() {
	cin >> N >> K;
	pow2[0] = 1;
	rep(i, 1, N * N + 1) pow2[i] = pow2[i - 1] * 2 % mod;
	dp[0][0] = 1;
	rep(i, 0, N) {
		rep(j, 0, K) {
			if(!dp[i][j]) continue;
			rep(k, i + 1, N + 1) {
				int a = k - i;
				ADD(dp[k][j + 1], dp[i][j] * (pow2[a] - 1 + mod) % mod * pow2[a * (N - k)] % mod);
			}
		}
	}
	ll res = 0;
	rep(i, 0, N + 1) {
		ADD(res, dp[i][K]);
	}
	cout << res << "\n";
}

CFの2000pointsくらいまで解けたらいいね。