Submission #3447223

---

Source Code Expand

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2005 + 10;
const int mod = 924844033;

int n, m, tot;
int tag[N], vis[N * 2];
int dp[N], g[N], fac[N], c[N][N], f[N * 2][N][2][2];

inline void Add(int &x, int y) {
	x = (x + y >= mod) ? (x + y - mod) : (x + y);
}

int main() {
	cin >> n >> m;
	c[0][0] = 1;
	for (int i = 1; i < N; ++i) {
		c[i][0] = 1;
		for (int j = 1; j <= i; ++j) {
			Add(c[i][j], c[i - 1][j]);
			Add(c[i][j], c[i - 1][j - 1]);
		}
	}
	fac[0] = 1;
	for (int i = 1; i < N; ++i)
		fac[i] = 1LL * fac[i - 1] * i % mod;
	for (int i = 1; i <= n; ++i) {
		if (vis[i]) continue;
		for (int j = i; j <= n; j += m) {
			tag[++tot] = 1;
			vis[j] = 1;
		}
		tag[tot] = 0;
	}
	f[0][0][1][0] = 1;
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= n; ++j) {
			for (int a = 0; a < 2; ++a) {
				for (int b = 0; b < 2; ++b) {
					int t = f[i][j][a][b];
					Add(f[i + 1][j][b][0], t);
					if (tag[i + 1])
						Add(f[i + 1][j + 1][b][1], t);
					if (tag[i])
						if (!a) Add(f[i + 1][j + 1][b][0], t);
				}
			}
		}
	}
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j < 2; ++j) {
			Add(dp[i], f[n][i][j][0]);
		}
	}
	// cout << n << endl;
	// // for (int i = 0; i <= n; ++i)
	// 	cout << dp[i] << ' ';
	// puts("");
	int ans = fac[n];
	for (int i = n; i >= 1; --i) {
		g[i] = 1LL * dp[i] * fac[n - i] % mod;
		if (i & 1) ans -= g[i];
		else ans += g[i];
		if (ans >= mod) ans -= mod;
		if (ans < 0) ans += mod;
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result