Submission #49003466

---

Source Code Expand

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 1e7 + 10;
const int M = 1e5 + 10;
const int P = 998244353;
void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
int ksm(int x, int k) {
  int res = 1;
  for(int pw = x; k; (k & 1) ? res = 1ll * res * pw % P : 0, pw = 1ll * pw * pw % P, k >>= 1);
  return res;
}
int fac[N], ifac[N];
void init() {
  fac[0] = ifac[0] = 1;
  for(int i = 1; i < N; i++)fac[i] = 1ll * fac[i - 1] * i % P;
  ifac[N - 1] = ksm(fac[N - 1], P - 2);
  for(int i = N - 2; i; i--)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
  return ;
}
int com(int n, int m) {return n < m || m < 0 ? 0 : 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;}
int n, m, k;
vector<pii> E;
int work1() {
  vector<int> val[2]; val[0].resize(k + 1); val[1].resize(k + 1);
  for(int i = 0; i <= k; i++)val[i & 1][i] = com(n + i - 1, n - 1);
  for(int i = 0; i < 2; i++)for(int j = 1; j <= k; j++)add(val[i][j], val[i][j - 1]);
  int ans = 0;
  for(int i = 0; i <= n; i++) {
    if(i * (m + 1) > k)break;
    int v = i * (m + 1), o = (i * (m + 1)) & 1;
    int w = 1ll * com(n, i) * val[o][k - v] % P;
    ((i & 1) ? sub(ans, w) : add(ans, w));
  }
  return ans;
}
int f[2][M][2], tmp[M][2];
void DP(int n, int L) {
  for(int i = 0; i < n; i++) {
    for(int j = 0; j <= L; j++)
      for(int o = 0; o < 2; o++) {
        f[1][j][o] = f[0][j][o];
        tmp[j][o] = f[0][j][o] = 0;
      }
    for(int j = 0; j <= L; j++) {
      for(int o = 0; o < 2; o++) {
        add(tmp[j][o ^ (j & 1)], f[1][j][o]);
        if(j > m)sub(tmp[j - m - 1][o ^ (j & 1)], f[1][j][o]);
      }
    }
    for(int j = L; ~j; j--) {
      for(int o = 0; o < 2; o++) {
        if(j < L)add(tmp[j][o], tmp[j + 1][o]);
        add(f[0][j][o ^ (j & 1)], tmp[j][o]);
      }
    }
  }
  return ;
}
int work2() {
  for(int i = 0; i <= m * 2; i++)
    for(int j = 0; j < 2; j++)
      f[0][i][j] = 0;
  for(int a = 0; a <= m; a++)
    for(int b = 0; b <= m; b++)
      if((a || b) && a + b <= k)
        f[0][min(k - a - b, a + b - 1)][(a + b) & 1]++;
  DP(n - 2, m * 2);
  int ans = 0;
  for(int i = 0; i <= m * 2; i++)add(ans, f[0][i][0]);
  return 1ll * n * ans % P;
}
int work3() {
  for(int i = 0; i <= m * 2; i++)
    for(int j = 0; j < 2; j++)
      f[0][i][j] = tmp[i][j] = 0;
  for(int a = 0; a <= m; a++) {
    for(int c = 0; c <= m; c++) {
      int x = min(a, c) - max(a, c) - 1, y = k - a - c, l, r;
      // cout << a << ' ' << c << ' ' << x << ' ' << y << endl;
      if(y - x >= 0) {
        l = x; r = x + min(m, (y - x) / 2);
        // cout << l << ' ' << r << endl;
        tmp[max(l, 0)][((a + c) ^ x) & 1]++;
        tmp[max(r + 1, 0)][((a + c) ^ x) & 1]--;
        l = y - m; r = max(l - 1, y - (y - x) / 2 - 1);
        tmp[max(l, 0)][((a + c) ^ y) & 1]++;
        tmp[max(r + 1, 0)][((a + c) ^ y) & 1]--;
      }
      else {
        l = y - m; r = max(l - 1, y);
        tmp[max(l, 0)][((a + c) ^ y) & 1]++;
        tmp[max(r + 1, 0)][((a + c) ^ y) & 1]--;
      }
    }
  }
  for(int i = 0; i <= m * 2; i++) {
    for(int j = 0; j < 2; j++) {
      if(i)add(tmp[i][j], tmp[i - 1][j]);
      add(f[0][i][j ^ (i & 1)], tmp[i][j]);
    }
  }
  DP(n - 3, m * 2);
  int ans = 0;
  for(int i = 0; i <= m * 2; i++)add(ans, f[0][i][0]);
  return 1ll * n * ans % P;
}
int main() {
  init();
  n = read(); m = read(); k = read();
  int ans = ((work1() - work2() + P) % P + work3()) % P;
  // int ans = work3();
  printf("%d\n", ans);
  return 0;
}

Submission Info

Judge Result