QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#641884#2590. 唱、跳、rap和篮球Elegia100 ✓2ms3924kbC++143.5kb2024-10-15 03:07:272024-10-15 03:07:28

Judging History

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

  • [2024-10-15 03:07:28]
  • 评测
  • 测评结果:100
  • 用时:2ms
  • 内存:3924kb
  • [2024-10-15 03:07:27]
  • 提交

answer

#include <bits/stdc++.h>

#define popcnt __builtin_popcount

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int P = 998244353;

int norm(int x) { return x >= P ? (x - P) : x; }

void add(int &x, int y) { if ((x += y) >= P) x -= P; }

void sub(int &x, int y) { if ((x -= y) < 0) x += P; }

void exGcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  exGcd(b, a % b, y, x);
  y -= a / b * x;
}

int inv(int a) {
  int x, y;
  exGcd(a, P, x, y);
  return norm(x + P);
}

const int N = 1010, K = 4;

int l[K], r[K];
int f[1 << K][N], g[1 << K][N];
int fac[N], ifac[N], nv[N];

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  for (int i = 0; i < K; ++i) cin >> r[i];

  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * (ull) i % P;
  ifac[n] = inv(fac[n]);
  for (int i = n; i; --i) ifac[i - 1] = ifac[i] * (ull) i % P;
  for (int i = 1; i <= n; ++i) nv[i] = ifac[i] * (ull) fac[i - 1] % P;

  int A = min(*min_element(r, r + K), n / K), B = sqrt(n);
  memcpy(l, r, sizeof(l));
  int ans = 0, U = (1 << K) - 1;
  g[0][0] = 1;
  for (int i = 0; i <= A; ++i) {
    if (i % B == 0) {
      memset(f, 0, sizeof(f));
      f[0][0] = 1;
      for (int s = 1; s != 1 << K; ++s) {
        f[s][0] = 1;
        int v = 1;
        int t = popcnt(s);
        for (int j = 1; j <= n - i * K; ++j) {
          v = v * (ull) t % P;
          for (int k = 0; k < K; ++k)
            if (s >> k & 1 && r[k] < j)
              v = (v + (P - ifac[r[k]]) * (ull) f[s ^ 1 << k][j - r[k] - 1]) % P;
          v = v * (ull) nv[j] % P;
          f[s][j] = v;
        }
      }
    }
    int w = f[U][n - i * K];

    if (i % B) {
      for (int s = 1; s != 1 << K; ++s) {
        int L = 0, R = 0, v = 1;
        for (int j = 0; j < K; ++j)
          if ((s >> j) & 1) {
            L += l[j] + 1;
            R += r[j];
            v = v * (ull) (P - ifac[l[j] + 1]) % P;
          }
        if (L > n - i * K) continue;
        g[s][L] = v;
        R = min(R, n - i * K);
        int t = popcnt(s);
        for (int j = L + 1; j <= R; ++j) {
          v = v * (ull) t % P;
          for (int k = 0; k < K; ++k)
            if (s >> k & 1) {
              if (l[k] < j) v = (v + (P - ifac[l[k]]) * (ull) g[s ^ 1 << k][j - l[k] - 1]) % P;
              if (r[k] < j) v = (v + ifac[r[k]] * (ull) g[s ^ 1 << k][j - r[k] - 1]) % P;
            }
          v = v * (ull) nv[j] % P;
          g[s][j] = v;
        }
        for (int j = L; j <= R; ++j)
          w = (w + g[s][j] * (ull) f[U ^ s][n - i * K - j]) % P;
      }
      for (int s = 1; s != 1 << K; ++s) {
        int L = 0, R = 0;
        for (int j = 0; j < K; ++j)
          if ((s >> j) & 1) {
            L += l[j] + 1;
            R += r[j];
          }
        if (L > n - i * K) continue;
        memset(g[s] + L, 0, sizeof(int) * (min(R, n - i * K) - L + 1));
      }
    }

    w = w * (ull) ifac[i] % P * fac[n - i * (K - 1)] % P;
    if (i & 1) sub(ans, w);
    else add(ans, w);
    for (int j = 0; j < K; ++j) --l[j];
    if ((i + 1) % B == 0) memcpy(r, l, sizeof(r));
  }
  cout << ans << '\n';

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

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

input:

7 2 6 8 7

output:

12176

result:

ok single line: '12176'

Test #2:

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

input:

8 8 8 8 8

output:

64257

result:

ok single line: '64257'

Test #3:

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

input:

13 2 9 7 10

output:

21225793

result:

ok single line: '21225793'

Test #4:

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

input:

20 6 3 9 5

output:

516020500

result:

ok single line: '516020500'

Test #5:

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

input:

14 5 8 1 10

output:

19436472

result:

ok single line: '19436472'

Test #6:

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

input:

930 490 275 473 441

output:

686063454

result:

ok single line: '686063454'

Test #7:

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

input:

853 420 252 120 139

output:

570353775

result:

ok single line: '570353775'

Test #8:

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

input:

900 307 481 236 499

output:

28060009

result:

ok single line: '28060009'

Test #9:

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

input:

195 458 380 385 44

output:

946454887

result:

ok single line: '946454887'

Test #10:

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

input:

231 231 231 231 231

output:

793921530

result:

ok single line: '793921530'