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

第11回情オリ本選対策14日目(あと使えるのは1日!)

JOI対策日記

明日が使えるという意見と使えないという意見があります。昨日は体調崩したりしていた。

POJ 3254、よく考えたら一昨日考えた解法間違ってたので、改めて書く。サンプルケースも通るのに何故かWA。何故だーーーーー
以下誤ソース。誰かデバッグしてー!(懇願)

#include <cstdio>
#include <vector>
#include <climits>
using namespace std;

int main()
{
	int N, M;
	scanf("%d %d\n", &M, &N);
	vector<bool> fertile;
	fertile.reserve(M * N);

	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < N; ++j) {
			int t;
			scanf("%d", &t);
			fertile.push_back((bool)t);
		}
	}

	// sentinel
	M++;
	fertile.reserve(M * N);
	for (int i = 0; i < N; ++i)
		fertile.push_back(false);

	const int MODULO = 100000000;
	vector<vector<int> > dp(2, vector<int>(1 << (N + 1), 0));
	int cur = 0, prev = 1;

	for (int i = 0, l = (1 << (N + 1)); i < l; ++i) {
		bool f = false;
		for (int j = 0; j < N + 1; ++j) {
			if (!(i & (1 << j)))
				continue;
			if (!fertile[N - j]) {
				f = true;
				break;
			}
		}
		if (f) continue;

		for (int j = 1; j < N; ++j) {
			if ((i & (3 << j)) == (3 << j)) {
				f = true;
				break;
			}
		}
		if (f) continue;
		if ((i & (1 << N)) && (i & 1)) continue;
		dp[prev][i] = 1;
	}

	for (int i = N + 1; i < fertile.size(); ++i) {
		for (int j = 0, l = (1 << (N + 1)); j < l; ++j) {
			if (j & 1) {
				if ((((j & 3) == 3) && (i % N != 0)) || (j & (1 << N)) || !fertile[i]) {
					dp[cur][j] = 0;
				} else {
					dp[cur][j] = (dp[prev][(1 << N) + (j >> 1)]
						   +  dp[prev][j >> 1]) % MODULO;
				}
			} else {
				dp[cur][j] = (dp[prev][(1 << N) + (j >> 1)]
					   +  dp[prev][j >> 1]) % MODULO;
			}
		}
		cur = !cur, prev = !prev;
	}
	int res = 0;

	for (int i = 0, l = (1 << (N + 1)); i < l; ++i)
		res = (res + dp[cur][i]) % MODULO;

	printf("%d\n", res);
	return 0;
}