QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#369544#1262. Justice For Everyoneyaoxi_stdAC ✓164ms9828kbC++144.5kb2024-03-28 14:09:542024-03-28 14:09:54

Judging History

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

  • [2024-03-28 14:09:54]
  • 评测
  • 测评结果:AC
  • 用时:164ms
  • 内存:9828kb
  • [2024-03-28 14:09:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define debug(fmt, ...) \
  fprintf(stderr, "[%d] " fmt "\n", __LINE__, ##__VA_ARGS__)
template <class _Tx, class _Ty>
inline void chkmin(_Tx& x, const _Ty& y) { if (y < x) x = y; }
template <class _Tx, class _Ty>
inline void chkmax(_Tx& x, const _Ty& y) { if (x < y) x = y; }
bool Mbe;
using ll = long long;
constexpr int N = 35, M = 205, mod = 998244353, inv2 = (mod + 1) >> 1;
int n, m, lmt, a[N], b[N], fac[N * M], ifac[N * M];
vector<int> f[M];
inline void add(int& x, int y) { x += y, x >= mod && (x -= mod); }
inline void sub(int& x, int y) { x -= y, x < 0 && (x += mod); }
inline int sum(int x, int y) { return x += y, x >= mod ? x - mod : x; }
inline int dif(int x, int y) { return x -= y, x < 0 ? x + mod : x; }
inline int neg(int x) { return x ? mod - x : 0; }
int qpow(int x, int y) {
  int ret = 1;
  for (; y; y >>= 1, x = (ll)x * x % mod)
    if (y & 1) ret = (ll)ret * x % mod;
  return ret;
}
namespace gs {
int a[N][N];
int det(int n) {
  int prd = 1;
  for (int i = 1; i <= n; ++i) {
    int p = i;
    for (int j = i; j <= n; ++j) if (a[j][i]) { p = j; break; }
    if (p != i) {
      prd = neg(prd);
      for (int j = i; j <= n; ++j) swap(a[i][j], a[p][j]);
    }
    if (!a[i][i]) return 0;
    prd = (ll)prd * a[i][i] % mod;
    int inv = qpow(a[i][i], mod - 2);
    for (int j = i; j <= n; ++j) a[i][j] = (ll)a[i][j] * inv % mod;
    for (int j = i + 1; j <= n; ++j) {
      int tmp = a[j][i];
      for (int k = i; k <= n; ++k) sub(a[j][k], (ll)a[i][k] * tmp % mod);
    }
  }
  return prd;
}
} // namespace gs
namespace poly {
constexpr int N = 1 << 14, g = 3;
int pwg[N];
inline int lg2(int x) { return x ? 31 - __builtin_clz(x) : -1; }
inline int getsz(int n) { return n ? 1 << (lg2(n - 1) + 1) : 0; }
void init() {
  for (int h = 2; h <= N; h <<= 1) {
    int gn = qpow(g, (mod - 1) / h);
    pwg[h >> 1] = 1;
    for (int i = (h >> 1) + 1; i < h; ++i) pwg[i] = (ll)pwg[i - 1] * gn % mod;
  }
}
void dft(vector<int>& f) {
  int n = f.size();
  for (int h = n; h >= 2; h >>= 1) {
    for (int i = 0, p = h >> 1; i < n; i += h) {
      for (int j = i; j < i + p; ++j) {
        int u = f[j], v = f[j + p];
        f[j] = sum(u, v), f[j + p] = (ll)pwg[j - i + p] * dif(u, v) % mod;
      }
    }
  }
}
void idft(vector<int>& f) {
  int n = f.size();
  for (int h = 2; h <= n; h <<= 1) {
    for (int i = 0, p = h >> 1; i < n; i += h) {
      for (int j = i; j < i + p; ++j) {
        int t = (ll)pwg[j - i + p] * f[j + p] % mod;
        f[j + p] = dif(f[j], t), add(f[j], t);
      }
    }
  }
  reverse(f.begin() + 1, f.end());
  for (int i = 0, k = qpow(n, mod - 2); i < n; ++i) f[i] = (ll)f[i] * k % mod;
}
struct _ { _() { init(); } } __;
} // namespace poly
bool Med;
int main() {
  // debug("Mem: %.4lfMB.", fabs(&Med - &Mbe) / 1048576);
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) cin >> b[i];
  m = *max_element(b + 1, b + n + 1) - *min_element(a + 1, a + n + 1);
  int tot = accumulate(b + 1, b + n + 1, 0) - accumulate(a + 1, a + n + 1, 0);
  if (tot & 1) return cout << "0\n", 0;
  tot >>= 1;
  for (int i = 1; i <= n; ++i) {
    if (a[i] > b[i]) return cout << "0\n", 0;
    for (int j = 1; j <= n; ++j) {
      if ((a[i] > a[j]) != (b[i] > b[j])) {
        return cout << "0\n", 0;
      }
    }
  }
  fac[0] = ifac[0] = ifac[1] = 1;
  for (int i = 1; i < N * M; ++i)
    fac[i] = (ll)fac[i - 1] * i % mod;
  for (int i = 2; i < N * M; ++i)
    ifac[i] = (ll)ifac[mod % i] * (mod - mod / i) % mod;
  for (int i = 2; i < N * M; ++i)
    ifac[i] = (ll)ifac[i - 1] * ifac[i] % mod;
  int lmt = poly::getsz(n * m + 1);
  for (int i = 0; i <= m; ++i) {
    f[i].resize(lmt);
    for (int j = 0; j + j <= i; ++j) {
      f[i][j] = (ll)ifac[j] * ifac[i - j * 2] % mod;
      if (j & 1) f[i][j] = neg(f[i][j]);
    }
    poly::dft(f[i]);
  }
  vector<int> g(lmt);
  for (int x = 0; x < lmt; ++x) {
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        gs::a[i][j] = 0;
        if (a[i] <= b[j]) gs::a[i][j] = f[b[j] - a[i]][x];
      }
    }
    g[x] = gs::det(n);
  }
  poly::idft(g);
  int ans = 0;
  for (int i = 0; i <= tot; ++i)
    ans = (ans + (ll)fac[2 * (tot - i)] * ifac[tot - i] % mod * g[i]) % mod;
  ans = (ll)ans * fac[tot] % mod * qpow(inv2, tot) % mod;
  cout << ans << '\n';
  return 0;
}
/*
g++ -std=c++14 -O2 -o qoj-1262 qoj-1262.cpp -Wall -Wextra
-Wshadow -fsanitize=address,undefined -g
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3668kb

input:

3
1 2 3
3 4 5

output:

1

result:

ok answer is '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

3
1 2 3
7 8 9

output:

42

result:

ok answer is '42'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

3
1 4 7
3 6 9

output:

6

result:

ok answer is '6'

Test #4:

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

input:

1
1
3

output:

0

result:

ok answer is '0'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

1
1
1

output:

1

result:

ok answer is '1'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3728kb

input:

2
1 4
4 7

output:

1

result:

ok answer is '1'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

10
10 9 8 7 6 1 2 3 4 5
11 12 13 114 115 120 129 128 127 126

output:

0

result:

ok answer is '0'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 131

output:

0

result:

ok answer is '0'

Test #9:

score: 0
Accepted
time: 75ms
memory: 5700kb

input:

30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130

output:

936606510

result:

ok answer is '936606510'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

30
16 21 33 44 51 60 71 81 91 100 110 122 131 144 155 160 162 171 172 174 177 179 187 188 189 191 192 193 194 199
110 111 112 113 114 115 116 117 118 119 120 122 131 144 155 160 162 171 172 174 177 179 187 188 189 191 192 193 194 199

output:

0

result:

ok answer is '0'

Test #11:

score: 0
Accepted
time: 164ms
memory: 9336kb

input:

30
16 21 33 44 51 60 71 81 91 100 110 122 131 144 155 160 162 171 172 174 177 179 187 188 189 191 192 193 194 199
110 111 112 113 114 115 116 117 118 119 120 122 131 144 155 160 162 171 172 174 177 179 187 188 189 191 192 193 194 200

output:

836228983

result:

ok answer is '836228983'

Test #12:

score: 0
Accepted
time: 7ms
memory: 4304kb

input:

10
10 9 8 7 6 5 4 3 2 1
110 109 108 107 106 105 104 103 102 101

output:

422463757

result:

ok answer is '422463757'

Test #13:

score: 0
Accepted
time: 161ms
memory: 9828kb

input:

30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200

output:

575061951

result:

ok answer is '575061951'