Submission #43383378

---

Source Code Expand

/** @file
 * @ingroup


 */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void O(const T &x) { cout << x << '\n'; }
template <typename T, typename... W> inline void O(const T &x, const W &...b) {
  cout << x << ' ';
  O(b...);
}
template <typename T> inline void rd(T &x) { cin >> x; }
template <typename T, typename... W> inline void rd(T &x, W &...b) {
  cin >> x;
  rd(b...);
}
#ifndef MISAKA
#define err(...)
#else
#define err(...) fprintf(stderr, __VA_ARGS__)
#endif
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef long double dbl;
typedef pair<int, int> pii;
typedef uniform_int_distribution<int> r32;
typedef uniform_int_distribution<i64> r64;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define shuf(L, R) shuffle((L), (R), rng)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define FOR(i, j, k) for (int i = (j); i <= (k); ++i)
#define ROF(i, j, k) for (int i = (k); i >= (j); --i)
template <typename T> inline void ckmin(T &a, const T &b) { a = min(a, b); }
template <typename T> inline void ckmax(T &a, const T &b) { a = max(a, b); }
//#define IOFILE "g"
//#define MULTI
const int N = 105;
const int p = 998244353;

int f[N][N][1<<9];
int fac[N];
int n, x;

inline void sol() {
  rd(n, x);
  fac[0] = fac[1] = 1;
  FOR(i,2,n) fac[i] = 1ll * fac[i-1] * i % p;
  --x;
  int r = 1 << (x*2+1);
  --r;
  FOR(i,0,n) f[i][0][0] = 1;
  FOR(i,1,n) FOR(j,1,i) FOR(u,0,r) {
    if (!(u >> (2*x))) {
      f[i][j][u] = (f[i-1][j][u<<1] + f[i-1][j][u<<1|1])%p;
      FOR(d,0,2*x) if (i-x+d>0 && i-x+d<=n) if ((u>>d)&1) {
        int v = (u ^ (1<<d)) <<1;
        f[i][j][u] = (1ll*f[i][j][u] + f[i-1][j-1][v] + f[i-1][j-1][v|1])%p;
      }
    }
    else if (i+x <= n) {
      int v = (u<<1) & r;
      f[i][j][u] = (f[i-1][j-1][v] + f[i-1][j-1][v|1]) % p;
    }
  }
  int ans = 0;
  FOR(i,0,n) {
    int c = 0;
    FOR(u,0,r) c = (c + f[n][i][u]) % p;
    c = 1ll * fac[n-i] * c % p;
    if (i&1) {
      ans = (ans + p - c) % p;
    } else {
      ans = (ans + c) % p;
    }
  }
  O(ans);
}

int main() {
#ifndef MISAKA
#ifdef IOFILE
  freopen(IOFILE ".in", "r", stdin);
  freopen(IOFILE ".out", "w", stdout);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
#endif
#ifdef MULTI
  int T;
  cin >> T;
  while (T--)
#endif
    sol();
  return 0;
}

Submission Info

Judge Result