読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 508 Div1 Medium: YetAnotherORProblem

解法

mayokoex.hatenablog.com

無理ゲー臭がすごい。

コード

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

}