Submission #1460552

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define e1 first
#define e2 second
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define eb emplace_back
#define OUT(x) {cout << x; exit(0); }
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long int ll;
typedef unsigned long long ull;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <PLL, int> PLLI;
typedef pair <PLL, PLL> PP;
typedef pair <PII, int> PPI;
typedef pair <ll, int> PLI;
typedef unsigned int ui;
const int inf = 1e9+9;
const int mod = 924844033;

const ll MOD = 1e9+696969;
const long long INF = 1e18+3;
ll fac[4010], invfac[4010];

ll potmod(ll a, ll b)
{
	ll res = 1;
	while (b > 0)
	{
		if (b & 1) res = (res * a ) % mod;
		a = (a * a)%mod;
		b /= 2;
	}
	return res;
}

inline ll binom(int n, int k)
{
	return fac[n] * invfac[k] % mod * invfac[n - k] % mod;
}
ll q[4010], c[4010], u, M[4010];

void mul(int x)
{
	int v = (x / 2) + 1;
	FOR(i, 0, v-1) q[i] = binom(x-i, i);
	FOR(i, 0, u+v-1) c[i] = 0;
	
	FOR(i, 0, u-1)
		FOR(j, 0, v-1) c[i+j] += (ll)M[i] * q[j], c[i+j]%=mod;
	
	FOR(i, 0, u+v-1) M[i] = c[i]; u += v-1;
}
int n, k;

int main()
{
	M[0] = 1; u = 1;
	fac[0] = 1; invfac[0] = 1;
	FOR(i, 1, 4000) 
	{
		fac[i] = fac[i-1] * i % mod;
		invfac[i] = potmod(fac[i], mod - 2);
	}
	boost;
	cin >> n >> k;
	FOR(i, 1, k)
	{
		int c = i, cnt = 0;
		while (c <= n) c+=k, ++cnt;
		mul(cnt);
		mul(cnt);
	}
	ll res = 0;
	for (int i=0; i<=n; ++i)
	{
		ll tmp = fac[n - i] * M[i]%mod;
		if (i & 1) res = (res + mod - tmp);
		else res += tmp;
		while (res >= mod) res -= mod;
	}
	cout << res;
	
}

Submission Info

Judge Result