QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#67526#2590. 唱、跳、rap和篮球alpha1022100 ✓7ms1768kbC++234.0kb2022-12-10 16:59:312022-12-10 16:59:35

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-10 16:59:35]
  • 评测
  • 测评结果:100
  • 用时:7ms
  • 内存:1768kb
  • [2022-12-10 16:59:31]
  • 提交

answer

#include <cmath>
#include <cstdio>
#include <algorithm>

using ll = long long;

using namespace std;

const int mod = 998244353;
inline int norm(int x) {
  return x >= mod ? x - mod : x;
}
inline int reduce(int x) {
  return x < 0 ? x + mod : x;
}
inline int neg(int x) {
  return x ? mod - x : 0;
}
inline void add(int &x, int y) {
  if ((x += y - mod) < 0)
    x += mod;
}
inline void sub(int &x, int y) {
  if ((x -= y) < 0)
    x += mod;
}
inline void fam(int &x, int y, int z) {
  x = (x + (ll)y * z) % mod;
}
inline int qpow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1)
    (b & 1) && (ret = (ll)ret * a % mod),
    a = (ll)a * a % mod;
  return ret;
}

const int N = 1e3;
const int K = 4;
const int MX = 2e3;
const int inf = 0x3f3f3f3f;

int n, a[K], mx, minAi, sumAi, lim, S;
int subsetSum[1 << K];
inline int lowbit(int x) {
  return x & -x;
}

int fac[MX + 5], ifac[MX + 5], inv[MX + 5];

int f[1 << K][N + 5], g[1 << K][N + 5];
int ans;

int main() {
  scanf("%d", &n);
  minAi = inf;
  for (int i = 0; i < K; ++i)
    scanf("%d", a + i), subsetSum[1 << i] = a[i], minAi = min(minAi, a[i]);
  for (int s = 0; s < (1 << K); ++s)
    subsetSum[s] = subsetSum[s ^ lowbit(s)] + subsetSum[lowbit(s)];
  sumAi = subsetSum[(1 << K) - 1];
  mx = max(n, subsetSum[(1 << K) - 1]);
  fac[0] = 1;
  for (int i = 1; i <= mx; ++i)
    fac[i] = (ll)fac[i - 1] * i % mod;
  ifac[mx] = qpow(fac[mx], mod - 2);
  for (int i = mx; i; --i)
    ifac[i - 1] = (ll)ifac[i] * i % mod;
  for (int i = 1; i <= mx; ++i)
    inv[i] = (ll)ifac[i] * fac[i - 1] % mod;
  lim = min(minAi, n / 4), S = sqrt(lim);
  for (int l = 0; l <= lim; l += S) {
    int low[1 << K];
    for (int s = 0; s < (1 << K); ++s)
      f[s][0] = 1;
    for (int k = 1; k <= sumAi - 4 * l && k <= n - 4 * l; ++k)
      for (int s = 0; s < (1 << K); ++s) {
        f[s][k] = (ll)__builtin_popcount(s) * f[s][k - 1] % mod;
        for (int i = 0; i < K; ++i)
          if (s & (1 << i) && a[i] - l < k)
            fam(f[s][k], f[s ^ (1 << i)][k - 1 - (a[i] - l)], neg(ifac[a[i] - l]));
        f[s][k] = (ll)f[s][k] * inv[k] % mod;
      }
    if (l & 1)
      ans = (ans - (ll)fac[n - 3 * l] * ifac[l] % mod * f[(1 << K) - 1][n - 4 * l] % mod + mod) % mod;
    else
      ans = (ans + (ll)fac[n - 3 * l] * ifac[l] % mod * f[(1 << K) - 1][n - 4 * l]) % mod;
    for (int r = l + 1; r < l + S && r <= lim; ++r) {
      int m = n - 4 * r, sum = 0;
      g[0][0] = 1;
      for (int i = 0; i < K; ++i)
        g[1 << i][a[i] - r + 1] = ifac[a[i] - r + 1];
      for (int s = 0; s < (1 << K); ++s) {
        low[s] = subsetSum[s] - __builtin_popcount(s) * (r - 1),
        g[s][low[s]] = (ll)g[s ^ lowbit(s)][low[s ^ lowbit(s)]] * g[lowbit(s)][low[lowbit(s)]] % mod;
        if (low[s] <= m && g[s][low[s]]) {
          if (__builtin_popcount(s) & 1)
            fam(sum, neg(g[s][low[s]]), f[((1 << K) - 1) ^ s][m - low[s]]);
          else
            fam(sum, g[s][low[s]], f[((1 << K) - 1) ^ s][m - low[s]]);
        }
      }
      for (int k = 1; k <= sumAi - 4 * l && k <= m; ++k)
        for (int s = 0; s < (1 << K); ++s)
          if (k < low[s])
            g[s][k] = 0;
          else if (k > low[s]) {
            g[s][k] = (ll)__builtin_popcount(s) * g[s][k - 1] % mod;
            for (int i = 0; i < K; ++i)
              if (s & (1 << i) && a[i] - r < k) {
                fam(g[s][k], g[s ^ (1 << i)][k - 1 - (a[i] - r)], ifac[a[i] - r]);
                if (a[i] - l < k)
                  fam(g[s][k], g[s ^ (1 << i)][k - 1 - (a[i] - l)], neg(ifac[a[i] - l]));
              }
            if (!g[s][k])
              continue;
            g[s][k] = (ll)g[s][k] * inv[k] % mod;
            if (__builtin_popcount(s) & 1)
              fam(sum, neg(g[s][k]), f[((1 << K) - 1) ^ s][m - k]);
            else
              fam(sum, g[s][k], f[((1 << K) - 1) ^ s][m - k]);
          }
      int coe = (ll)fac[m + r] * ifac[r] % mod;
      if (r & 1)
        coe = neg(coe);
      fam(ans, coe, sum);
    }
  }
  printf("%d\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 1ms
memory: 1596kb

input:

7 2 6 8 7

output:

12176

result:

ok single line: '12176'

Test #2:

score: 10
Accepted
time: 1ms
memory: 1660kb

input:

8 8 8 8 8

output:

64257

result:

ok single line: '64257'

Test #3:

score: 10
Accepted
time: 1ms
memory: 1668kb

input:

13 2 9 7 10

output:

21225793

result:

ok single line: '21225793'

Test #4:

score: 10
Accepted
time: 0ms
memory: 1672kb

input:

20 6 3 9 5

output:

516020500

result:

ok single line: '516020500'

Test #5:

score: 10
Accepted
time: 1ms
memory: 1680kb

input:

14 5 8 1 10

output:

19436472

result:

ok single line: '19436472'

Test #6:

score: 10
Accepted
time: 5ms
memory: 1668kb

input:

930 490 275 473 441

output:

686063454

result:

ok single line: '686063454'

Test #7:

score: 10
Accepted
time: 7ms
memory: 1736kb

input:

853 420 252 120 139

output:

570353775

result:

ok single line: '570353775'

Test #8:

score: 10
Accepted
time: 2ms
memory: 1768kb

input:

900 307 481 236 499

output:

28060009

result:

ok single line: '28060009'

Test #9:

score: 10
Accepted
time: 0ms
memory: 1672kb

input:

195 458 380 385 44

output:

946454887

result:

ok single line: '946454887'

Test #10:

score: 10
Accepted
time: 1ms
memory: 1764kb

input:

231 231 231 231 231

output:

793921530

result:

ok single line: '793921530'