解法
d.hatena.ne.jp
DPする。総和をとるところで式を工夫して、問題数の少ない方から埋めていくとO(MAX_P)で計算することができる。
コード
public class SRMIntermissionPhase {
private final long MOD = (int) 1e9 + 7;
public int countWays(int[] points, String[] description) {
int N = description.length;
int MAX_P = points[0] + points[1] + points[2];
int[] states = new int[N];
for (int i = 0; i < N; i++) {
int bit = 0;
for (int j = 0; j < 3; j++) {
if (description[i].charAt(j) == 'Y') {
bit |= 1 << j;
}
}
states[i] = bit;
}
long[][] ways = new long[1 << 3][MAX_P + 1];
ways[0][0] = 1;
for (int bit = 1; bit < 8; bit++) {
int left = 2;
while (((bit >> left) & 1) == 0) {
left--;
}
int prevBit = bit ^ (1 << left);
for (int point = 1; point <= MAX_P; point++) {
ways[bit][point] = ways[bit][point - 1];
ways[bit][point] += ways[prevBit][point - 1];
int lowest = point - points[left];
if (lowest > 0) {
ways[bit][point] -= ways[prevBit][lowest - 1];
}
}
}
long[] from = ways[states[0]];
for (int i = 1; i < N; i++) {
long[] next = new long[MAX_P + 1];
long sum = 0;
for (int point = MAX_P; point >= 0; point--) {
next[point] = sum * ways[states[i]][point] % MOD;
sum = (sum + from[point]) % MOD;
}
from = next;
}
long ans = 0;
for (int i = 0; i <= MAX_P; i++) {
ans = (ans + from[i]) % MOD;
}
return (int) ans;
}
}