Submission #4035891

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 924844033
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

Int fact[1080000];
Int revfact[1080000];
Int rev[1080000];

void init(){
  Int m = MOD;
  fact[0] = 1;
  revfact[0] = 1;
  rev[0] = 0;
  rev[1] = 1;
  for(int i = 1;i < 1080000;i++){
    fact[i] = fact[i-1] * i % m;
    if(i>1)rev[i] = MOD / i * (MOD-rev[MOD % i]) % MOD;
    revfact[i] = revfact[i-1] * rev[i] % MOD;
  }
}

Int nCk(Int n, Int k){
  if(n < k)return 0;
  return fact[n] * revfact[n-k] % MOD * revfact[k] % MOD;
}


Int dp[2160][2];
Int n, k, K;
int main(){
  init();
  dp[0][0] = 1;
  cin >> n >> K;
  for(int i = 0;i < K*2;i++){
    for(int j = i;j < n;j += 2*K){
      for(int k = n;k >= 1;k--){
	dp[k][0] = (dp[k][0] + dp[k][1]) % MOD;
	if(j >= K)dp[k][0] = (dp[k][0] + dp[k-1][0]) % MOD;
	if(K <= j && j < 2*K)dp[k][0] = (dp[k][0] + dp[k-1][1]) %MOD;
	if(j + K < n)dp[k][1] = (dp[k-1][0] + dp[k-1][1])%MOD;
	else dp[k][1] = 0;
      }
    }
  }

  Int cnt = fact[n];
  for(int i = 1;i <= n;i++){
    if(i % 2 == 1)cnt -= (dp[i][0] + dp[i][1]) * fact[n-i]%MOD;
    else cnt += (dp[i][0] + dp[i][1]) * fact[n-i] %MOD;
    cnt %= MOD;
  }
  if(cnt < 0)cnt += MOD;
  cout << cnt << endl;
  return 0;
}

Submission Info

Judge Result