Submission #32037475

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 1e3;
const int MAXm = 5e3;
const int MOD = 998244353;

template <typename T>
inline void read(T &a) {
	char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
	read(a), read(argv...);
}

inline int addmod(int x) {
	if (x >= MOD) return x - MOD;
	else return x;
}
inline int redmod(int x) {
	if (x < 0) return x + MOD;
	else return x;
}

inline int power(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = ans * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return ans;
}

int n, m, z;

struct Trecter {
	int t[MAXm + 10];
	inline int lowbit(int x) {
		return x & -x;
	}
	void clear() {
		memset(t, 0, sizeof(int) * (m + 1));
	}
	void modifyAdd(int p, int v) {
		if (p > m) return;
		while (p <= m) {
			t[p] = addmod(t[p] + v);
			p += lowbit(p);
		}
	}
	int querySum(int p) {
		if (p <= 0) return 0;
		int ans = 0;
		while (p) {
			ans = addmod(ans + t[p]);
			p -= lowbit(p);
		}
		return ans;
	}
	int querySec(int l, int r) {
		return redmod(querySum(r) - querySum(l - 1));
	}
} d[2];

signed main() {
	read(n, m, z);
	if (z == 0) {
		printf("%lld\n", power(m, n));
	} else {
		int i = 1;
		int now = 0, last = 1;
		for (int j = 1; j <= m; ++j) {
			d[now].modifyAdd(j, 1);
		}
		for (++i, now ^= 1, last ^= 1; i <= n; ++i, now ^= 1, last ^= 1) {
			d[now].clear();
			for (int j = 1; j <= m; ++j) {
				int l1 = 1, r1 = j - z;
				int l2 = j + z, r2 = m;
				int D = 0;
				if (l1 <= r1) D = addmod(D + d[last].querySec(l1, r1));
				if (l2 <= r2) D = addmod(D + d[last].querySec(l2, r2));
				d[now].modifyAdd(j, D);
			}
		}
		int ans = d[last].querySec(1, m);
		printf("%lld\n", ans);
	}
}

Submission Info

Judge Result