SRM520 Div1 Medium

500
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];
  }
};