http://community.topcoder.com/stat?c=problem_statement&pm=11496&rd=14545
DP1[どれを解いた][ポイント] = あるポイント以下を取るパターン数
DP2[何人目まで見た][ポイント] = パターン数
まず、幾らかの問題を解いてあるポイントを取るパターン数を数え上げる。
問題 i のポイントのとり方は、(1, points[i]) の区間。
注目しているポイントを p とすると、テーブルの更新にはそれまでの (p - 1, p - points[i]) の区間の総和が必要。
BITで挑戦するも、意外と遅くて方針転換。
ある区間の総和は、累積和で計算する。
DP1[bit | (1 << i)][p] = (DP1[bit][p - 1] - DP1[bit][p - 1 - points[i]]) + DP1[bit | (1 << i)][p - 1]
加算の左辺値が区間の和で、右辺値が累積
※この累積和の区間はinclusive
次に、全体のパターン数を数える。
n番目の参加者は(n - 1)番目の参加者よりも大きいポイントを取っているはず。
n番目の参加者がポイントを p だけ取得しているとすると、(n - 1)番目の参加者が p 未満のポイントを取った場合のパターン数の総和が必要。
また総和が必要なので累積和をまた使う。
DP2[c][p] = DP2[c][p - 1] + DP2[c - 1][p - 1] * (ポイント p の作り方)
加算の左辺値が累積で、右辺値がポイント p を取るパターン数
ポイント p の作り方は最初の累積和から、 (DP1[bit][p] - DP1[bit][p - 1])で計算できる。
難しかった。
class SRMIntermissionPhase { public: int countWays(vector <int> ps, vector <string> desc) { const lli mod = 1000000007; const int B = 1 << 3; const int N = 20 + 5; const int M = 30000 + 60000 + 110000 + 10; const int C = desc.size(); static lli dp1[B][M]; fill(&dp1[0][0], &dp1[B - 1][M - 1] + 1, 0); dp1[0][0] = 1; for (int p = 1; p < M; ++p) { dp1[0][p] += dp1[0][p - 1]; } for (int b = 0; b < B; ++b) { dp1[b][__builtin_popcount(b)] = 1; } for (int b = 0; b < B; ++b) { for (int p = 1; p < M; ++p) { if (dp1[b][p] == 0) continue; for (int i = 0; i < 3; ++i) { unless (b & (1 << i)) { if (0 <= p - 1 - ps[i]) { dp1[b | (1 << i)][p] = (dp1[b][p - 1] - dp1[b][p - 1 - ps[i]] + mod); } else { dp1[b | (1 << i)][p] = dp1[b][p - 1]; } dp1[b | (1 << i)][p] += dp1[b | (1 << i)][p - 1]; dp1[b | (1 << i)][p] %= mod; } } } } reverse(desc.begin(), desc.end()); static lli dp2[N][M]; fill(&dp2[0][0], &dp2[N - 1][M - 1] + 1, 0); dp2[0][0] = 1; for (int p = 1; p < M; ++p) { dp2[0][p] += dp2[0][p - 1]; } for (int c = 0; c < C; ++c) { int b = 0; if (desc[c][0] == 'Y') b |= (1 << 0); if (desc[c][1] == 'Y') b |= (1 << 1); if (desc[c][2] == 'Y') b |= (1 << 2); if (b == 0 && c) return 0; { int p = 0; dp2[c + 1][__builtin_popcount(b)] = dp2[c][p]; } for (int p = 1; p + 1 < M; ++p) { lli x = (dp2[c][p - 1] * ((dp1[b][p] - dp1[b][p - 1] + mod) % mod)) % mod; dp2[c + 1][p] = dp2[c + 1][p - 1] + x; dp2[c + 1][p] %= mod; } } int p = 0; if (desc[C - 1][0] == 'Y') p += ps[0]; if (desc[C - 1][1] == 'Y') p += ps[1]; if (desc[C - 1][2] == 'Y') p += ps[2]; return dp2[C][p]; } };