QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#24763#1839. Jokealpha1022WA 2ms3748kbC++141.1kb2022-04-02 22:25:562022-04-30 06:34:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 06:34:42]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3748kb
  • [2022-04-02 22:25:56]
  • 提交

answer

#include <cstdio>

using ll = long long;

using namespace std;

const int mod = 998244353;
inline void add(int &x, int y) {
  if ((x += y - mod) < 0)
    x += mod;
}

const int N = 101;

int n;
int p[N + 5], q[N + 5], cnt;
bool vis[N + 5];
int f[N + 5][N + 5][N + 5];
int ans;

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", p + i);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    q[p[i]] = x, cnt += !x, vis[x] = 1;
  }
  q[n + 1] = n + 1;
  f[0][0][0] = 1;
  for (int i = 1; i <= n + 1; ++i)
    for (int j = 0; j <= cnt; ++j) {
      for (int w = 0; w <= n; ++w)
        f[i][j][w] = f[i - 1][j][w];
      if (q[i])
        for (int w = 0; w < q[i]; ++w)
          add(f[i][j][q[i]], f[i - 1][j][w]);
      else
        for (int w = 1, s = 0; w <= n; ++w) {
          add(s, f[i - 1][j - 1][w - 1]);
          if (!vis[w])
            add(f[i][j][w], s);
        }
    }
  ans = f[n + 1][cnt][n + 1];
  for (int i = 1, fac = 1; i <= cnt; ++i)
    fac = (ll)fac * i % mod,
    ans = (ans + (ll)fac * f[n + 1][cnt - i][n + 1]) % mod;
  printf("%d\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 1812kb

input:

2
1 2
2 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

4
4 3 2 1
4 3 2 1

output:

16

result:

ok 1 number(s): "16"

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 3748kb

input:

5
1 2 3 4 5
0 0 0 0 0

output:

550453442

result:

wrong answer 1st numbers differ - expected: '1546', found: '550453442'