TopCoder SRM 508 Div1 Medium: YetAnotherORProblem
コード
public class YetAnotherORProblem { private final long MOD = 1000000009; private final int MAX_D = 61; public int countSequences(long[] R) { int N = R.length; int M = 1 << N; long[][] dp = new long[MAX_D + 1][M]; dp[MAX_D][0] = 1;// MAX_Dまで来た時に残っているA[i]は存在しない for (int digit = MAX_D - 1; digit >= 0; digit--) { for (int remain = 0; remain < M; remain++) { for (int i = 0; i <= N; i++) { /* * 上からdigit桁目を見た時に remain のように残っていて、A[i]のdigitを1にする場合を考える */ boolean isAllZero = i == N;// 全てのAのdigitが0 boolean isRemain = i < N && ((remain >> i) & 1) == 1;// A[i]のdigitを1にすることができる(残っている) boolean willRemain = i < N && ((R[i] >> digit) & 1) == 1;// 今は残っていなくても以降残る場合 if (isAllZero || isRemain || willRemain) { int nextRemain = remain; for (int k = 0; k < N; k++) { if (k == i) { // A[i]を1にする場合、以降で残るかわからないのでスルー continue; } if (((R[k] >> digit) & 1) == 1) { // 今残っていなくても次以降で残る場合 nextRemain |= (1 << k); } } dp[digit][nextRemain] += dp[digit + 1][remain]; dp[digit][nextRemain] %= MOD; } } } } long ans = 0; for (int remain = 0; remain < M; remain++) { ans += dp[0][remain]; ans %= MOD; } return (int) ans; } }