BZOJ1494 failing dp

bzoj1494_baoli.cpp

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const ll mod = 65521;

inline ll pow(ll a, ll b) {
	ll ret = 1;
	for(; b; b >>= 1, a = a * a % mod) if(b & 1) ret = ret * a % mod;
	return ret;
}

const int N = 100 + 5;

int k, n;
ll mt[N][N];

int main() {
	scanf("%d%d", &k, &n);
	for(int i = 1; i <= n; ++i) for(int j = i + 1; j <= min(n, i + k); ++j) {
		--mt[i][j], --mt[j][i];
		++mt[i][i], ++mt[j][j];
	}
	ll ans = 1;
	for(int i = 1; i < n; ++i) {
		int jid = -1;
		for(int j = i; j < n; ++j) if(mt[j][i]) { jid = j; break; }
		if(jid != i) for(int j = 1; j < n; ++j) swap(mt[i][j], mt[jid][j]);
		ans = ans * mt[i][i] % mod;
		ll i_mtii = pow(mt[i][i], mod - 2);
		for(int j = 1; j < n; ++j) mt[i][j] = mt[i][j] * i_mtii % mod;
		for(int kk = 1; kk < n; ++kk) if(kk != i) {
			ll mtkki = mt[kk][i];
			for(int j = 1; j < n; ++j) mt[kk][j] = (mt[kk][j] - mt[i][j] * mtkki % mod + mod) % mod;
		}
	}
	printf("%lld\n", (ans % mod + mod) % mod);
	return 0;
}

bzoj1494_baoli_dp.cpp

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const ll mod = 65521;

inline ll pow(ll a, ll b) {
	ll ret = 1;
	for(; b; b >>= 1, a = a * a % mod) if(b & 1) ret = ret * a % mod;
	return ret;
}

const int N = 100 + 5, K = 5, S = (1 << (2 * K)) + 1;

int kbd, n;

ll f[N][S];

inline int g_mt(int i, int j) {
	if(i == j) return min(n, i + kbd) - max(1, i - kbd);
	else return abs(i - j) <= kbd ? mod - 1 : 0;
}

int popcount[S];

int main() {
	scanf("%d%d", &kbd, &n);
	f[1][(1 << kbd) - 1] = 1;
	for(int s = 1; s < (1 << (kbd * 2)); ++s) popcount[s] = popcount[s >> 1] + (s & 1);
	for(int i = 1; i < n - 1; ++i) for(int s = 0; s < (1 << (kbd * 2)); ++s) if(f[i][s]) {
		for(int j = -kbd; j <= kbd; ++j) if(i + j >= 1 && i + j < n && !(s >> (j + kbd) & 1) && ((s | 1 << (j + kbd)) & 1)) {
			ll &nxt = f[i + 1][(s | 1 << (j + kbd)) >> 1], ths = f[i][s];
			nxt = (nxt + ths * g_mt(i, i + j) % mod * pow(mod - 1, popcount[s >> (j + kbd + 1)])) % mod;
		}
	}
	printf("%lld\n", f[n - 1][(1 << kbd) - 1]);
	return 0;
}