QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#86798#5408. 计数鸡Scintilla0 2ms3696kbC++141.7kb2023-03-10 22:52:042023-03-10 22:52:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-10 22:52:08]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:3696kb
  • [2023-03-10 22:52:04]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

const int P = 998244353;

const int N = 3e2 + 10;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

int inc(int a, int b) { return (a += b) >= P ? a - P : a; }
int dec(int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul(int a, int b) { return 1ll * a * b % P; }
int qpow(int a, int b) { int res = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a); return res; }

int n, p[N], h[N], a[N][N], ans, fac = 1;

int det() {
  int res = 1;
  rep(i, 1, n) {
    if (!a[i][i]) {
      rep(j, i + 1, n) if (a[j][i]) {
        swap(a[i], a[j]), res = mul(res, P - 1);
        break;
      }
      if (!a[i][i]) return 0;
    }
    rep(j, i + 1, n) {
      int t = mul(a[j][i], qpow(a[i][i], P - 2));
      rep(k, i, n) a[j][k] = dec(a[j][k], mul(a[i][k], t));
    }
  }
  rep(i, 1, n) res = mul(res, a[i][i]);
  return res;
}

int main() {
  n = read();
  rep(i, 1, n) p[i] = read();
  rep(i, 1, n) h[i] = read();
  rep(i, 1, n) rep(x, 1, n) {
    rep(j, i + 1, n) a[i][j] ^= x + h[i] >= p[j];
  }
  ans = det();
  rep(i, 1, n) fac = mul(fac, i);
  printf("%d\n", mul(inc(ans, fac), (P + 1) / 2));
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 20
Accepted
time: 2ms
memory: 3508kb

input:

20
20 4 15 16 11 3 7 18 9 5 13 8 6 12 2 10 1 17 14 19
-7 -11 9 -3 -20 -13 -18 15 0 8 0 12 -16 -19 8 -9 -4 -2 6 -10

output:

699910446

result:

ok 1 number(s): "699910446"

Test #2:

score: -20
Wrong Answer
time: 1ms
memory: 3516kb

input:

20
11 6 3 18 17 19 4 8 10 15 12 16 1 13 7 14 5 20 9 2
13 9 -1 1 9 -11 -19 8 -5 -11 -4 3 17 1 8 1 0 -11 -16 -10

output:

699910446

result:

wrong answer 1st numbers differ - expected: '694405422', found: '699910446'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 30
Accepted
time: 0ms
memory: 3452kb

input:

15
14 4 15 10 11 3 7 1 9 5 13 8 6 12 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

output:

985377138

result:

ok 1 number(s): "985377138"

Test #12:

score: -30
Wrong Answer
time: 2ms
memory: 3696kb

input:

15
1 2 12 4 8 13 6 5 9 3 11 10 7 14 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

output:

985377138

result:

wrong answer 1st numbers differ - expected: '985385330', found: '985377138'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%