QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#622745#1839. JokevaleriuAC ✓17ms13700kbC++203.5kb2024-10-09 01:34:432024-10-09 01:34:43

Judging History

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

  • [2024-10-09 01:34:43]
  • 评测
  • 测评结果:AC
  • 用时:17ms
  • 内存:13700kb
  • [2024-10-09 01:34:43]
  • 提交

answer

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

//#ifndef DLOCAL
//   #define cin fin
//   #define cout fout
//   ifstream cin(".in");
//   ofstream cout(".out");
//#endif

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int mod = 998244353;
struct Mint {
   int val;
   Mint(ll x = 0): val((x % mod + mod) % mod) {;}
   Mint operator +(const Mint& x) const { return Mint(val + x.val); }
   Mint operator -(const Mint& x) const { return Mint(val - x.val); }
   Mint operator *(const Mint& x) const { return Mint((ll)val * x.val); }
   Mint operator +=(const Mint& x) { return *this = Mint(val + x.val); }
   Mint operator -=(const Mint& x) { return *this = Mint(val - x.val); }
   Mint operator *=(const Mint& x) { return *this = Mint((ll)val * x.val); }
   Mint operator ^(int b) const {
      Mint accum = 1, a = *this;
      while(b) {
         accum = (b & 1? accum * a : accum);
         a *= a;
         b >>= 1;
      }
      return accum;
   }
   Mint operator /(const Mint& x) { return Mint((ll)val * (x ^ (mod - 2)).val); }
   Mint operator /=(const Mint& x) { return *this = Mint((ll)val * (x ^ (mod - 2)).val); }
};
namespace COMBI {
   const int nmax = 1e5 + 5;  
   Mint fact[nmax], invfact[nmax];
   void init(int n = nmax - 1) {
      fact[0] = 1;
      for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
      invfact[n] = Mint(1) / fact[n];
      for(int i = n; i > 0; i--) invfact[i - 1] = invfact[i] * Mint(i);
      return;
   }
   Mint f(int n) { return fact[n]; }
   Mint invf(int n) { return invfact[n]; }
   Mint ncr(int n, int r) { return fact[n] * invfact[r] * invfact[n - r]; }
}

const int nmax = 1e2 + 5;

Mint dp[nmax][nmax][nmax];
Mint spart[nmax][nmax][nmax];



signed main() {
   COMBI::init();
   cin.tie(0) -> sync_with_stdio(0);
   int n;
   cin >> n;
   
   vector<pii> val(n + 1);
   for(auto &[x, y] : val | views::drop(1)) cin >> x;
   for(auto &[x, y] : val | views::drop(1)) cin >> y;
   sort(1 + all(val));
   
   vector<int> second;
   {
      vector<int> freq(n + 1);
      for(auto &[a, b] : val) freq[b] = 1;
      for(int i = 1;  i <= n; i++) if(!freq[i]) second.emplace_back(i);
   }
   
   dp[0][0][0] = 1;
   for(int i = 0; i <= n; i++) spart[0][i][0] = 1;
   Mint total = COMBI::f(sz(second));
   
   for(int i = 1; i <= n; i++) {
      for(int chosen = 0; chosen <= min(sz(second), i); chosen++) {
         if(val[i].second != 0) {
            cerr << i << ' ' << val[i].second << ' ' << chosen << '\t' << spart[i - 1][val[i].second - 1][chosen].val << '\n';
            dp[i][val[i].second][chosen] += spart[i - 1][val[i].second - 1][chosen];
         }
         else if(chosen > 0) {
            for(auto x : second) dp[i][x][chosen] += spart[i - 1][x - 1][chosen - 1];
         }
      }
      for(int chosen = 0; chosen <= min(sz(second), i); chosen++) {
         for(int dim = 0; dim <= n; dim++) {
            total += dp[i][dim][chosen] * COMBI::f(sz(second) - chosen);
            spart[i][dim][chosen] = dp[i][dim][chosen];
            spart[i][dim][chosen] += spart[i - 1][dim][chosen];
            if(dim > 0) spart[i][dim][chosen] += spart[i][dim - 1][chosen] - spart[i - 1][dim - 1][chosen];
         }
      }
   }
   
   cout << total.val << '\n';
}

//10 + 9

//1 2 3 4
//2 3 4 1 




/**
      Ovaj podrum ima hladan sjaj\Iako je to bolje od gomile drugih
--
*/ 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 13468kb

input:

2
1 2
2 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

4
4 3 2 1
4 3 2 1

output:

16

result:

ok 1 number(s): "16"

Test #3:

score: 0
Accepted
time: 2ms
memory: 13472kb

input:

5
1 2 3 4 5
0 0 0 0 0

output:

1546

result:

ok 1 number(s): "1546"

Test #4:

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

input:

6
1 6 2 5 3 4
0 1 0 2 0 3

output:

52

result:

ok 1 number(s): "52"

Test #5:

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

input:

10
8 2 10 3 4 6 1 7 9 5
0 0 0 0 0 0 0 0 0 0

output:

234662231

result:

ok 1 number(s): "234662231"

Test #6:

score: 0
Accepted
time: 6ms
memory: 13396kb

input:

10
5 8 4 9 6 1 2 7 3 10
8 3 0 5 0 9 0 0 6 0

output:

5294

result:

ok 1 number(s): "5294"

Test #7:

score: 0
Accepted
time: 3ms
memory: 13460kb

input:

10
4 2 6 9 5 3 8 1 10 7
0 9 8 0 7 3 4 2 1 10

output:

166

result:

ok 1 number(s): "166"

Test #8:

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

input:

10
8 2 7 1 5 9 3 4 10 6
7 0 2 9 5 1 8 4 3 6

output:

26

result:

ok 1 number(s): "26"

Test #9:

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

input:

10
10 1 6 7 9 8 4 3 5 2
2 5 1 3 9 10 4 8 6 7

output:

47

result:

ok 1 number(s): "47"

Test #10:

score: 0
Accepted
time: 6ms
memory: 13504kb

input:

50
41 15 17 1 5 31 7 38 30 39 43 35 2 26 20 42 48 25 19 32 50 4 8 10 44 12 9 18 13 36 28 6 27 23 40 24 3 14 29 11 49 47 45 46 34 21 37 16 22 33
0 0 0 0 0 0 0 0 0 33 34 0 0 0 0 0 0 0 0 0 0 2 0 0 0 20 0 0 28 0 0 0 9 0 0 0 48 0 0 0 50 0 0 0 0 5 0 0 32 0

output:

976189245

result:

ok 1 number(s): "976189245"

Test #11:

score: 0
Accepted
time: 5ms
memory: 13652kb

input:

50
36 35 13 14 45 44 22 10 30 23 15 17 6 42 8 49 21 46 5 32 25 34 38 4 48 50 28 3 9 24 43 47 20 2 40 37 29 41 26 7 39 33 31 19 27 16 11 12 1 18
0 0 0 19 20 42 0 18 9 0 27 0 38 0 0 45 0 33 0 0 0 0 0 7 0 0 37 41 0 2 0 1 0 0 5 13 8 0 0 0 0 0 0 15 17 0 12 0 0 0

output:

861991745

result:

ok 1 number(s): "861991745"

Test #12:

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

input:

50
24 4 17 27 45 5 8 33 7 23 19 42 11 2 39 38 48 37 32 29 18 47 6 36 25 15 31 50 12 3 44 28 30 41 40 16 14 21 46 22 34 9 43 26 49 35 10 1 20 13
15 0 0 19 0 0 0 0 0 5 3 0 31 0 25 26 41 7 9 0 22 0 11 49 24 0 43 13 14 35 16 0 27 0 0 0 47 0 0 18 20 23 33 42 36 8 0 30 44 0

output:

231982952

result:

ok 1 number(s): "231982952"

Test #13:

score: 0
Accepted
time: 5ms
memory: 13404kb

input:

50
37 9 29 2 13 35 7 16 12 42 34 47 14 46 27 6 21 32 15 49 20 10 31 48 18 4 23 40 25 30 50 41 24 26 11 5 33 36 8 22 39 3 17 43 44 1 45 28 19 38
50 33 0 0 14 10 13 15 16 0 35 12 5 9 34 6 0 38 21 22 45 0 0 28 31 36 0 43 29 37 7 1 20 44 11 4 40 2 0 17 27 39 0 3 30 0 24 26 25 18

output:

31263262

result:

ok 1 number(s): "31263262"

Test #14:

score: 0
Accepted
time: 2ms
memory: 13352kb

input:

50
24 47 6 19 1 25 42 38 18 2 7 3 13 27 23 48 28 36 45 39 37 29 16 12 15 10 8 46 33 34 43 14 50 9 31 32 44 20 26 4 40 22 17 49 35 41 11 21 5 30
7 47 5 19 31 9 48 14 32 11 12 13 33 36 42 29 26 24 39 46 28 15 50 8 30 22 35 3 4 43 10 38 41 6 21 20 2 27 16 37 23 17 45 34 49 40 25 18 44 1

output:

78388

result:

ok 1 number(s): "78388"

Test #15:

score: 0
Accepted
time: 12ms
memory: 13468kb

input:

100
11 9 35 34 51 74 16 67 26 21 14 80 84 79 7 61 28 3 53 43 42 5 56 36 69 30 22 88 1 27 65 91 46 31 59 50 17 96 25 18 64 55 78 2 63 24 95 48 93 13 38 76 89 94 15 90 45 81 52 87 83 73 44 49 23 82 85 75 86 33 47 19 58 97 37 20 40 10 92 4 6 68 77 54 71 12 62 60 100 39 41 99 72 29 57 8 70 32 66 98
0 0 ...

output:

452312947

result:

ok 1 number(s): "452312947"

Test #16:

score: 0
Accepted
time: 12ms
memory: 13696kb

input:

100
78 52 95 76 96 49 53 59 77 100 64 11 9 48 15 17 44 46 21 54 39 68 43 4 32 28 73 6 16 62 72 84 65 86 98 75 33 45 25 3 91 82 2 92 63 88 7 50 97 93 14 22 20 42 60 55 80 85 29 34 56 71 83 38 26 47 90 70 51 41 40 31 37 12 35 99 67 94 1 87 57 8 61 19 23 79 36 18 66 74 5 27 81 69 24 58 13 10 89 30
0 0 ...

output:

366370216

result:

ok 1 number(s): "366370216"

Test #17:

score: 0
Accepted
time: 13ms
memory: 13392kb

input:

100
62 70 29 14 12 87 94 78 39 92 84 91 61 49 60 33 69 37 19 82 42 8 45 97 81 43 54 67 1 22 77 58 65 17 18 28 25 57 16 90 40 13 4 21 68 35 15 76 73 93 56 95 79 47 74 75 30 71 66 99 41 24 88 83 5 6 31 96 38 80 27 46 51 53 2 86 32 9 20 100 26 36 63 7 52 55 23 3 50 59 48 89 85 44 34 64 10 72 11 98
0 0 ...

output:

351981437

result:

ok 1 number(s): "351981437"

Test #18:

score: 0
Accepted
time: 12ms
memory: 13356kb

input:

100
100 6 41 33 5 32 39 58 95 48 27 17 90 73 10 81 56 87 79 91 43 42 47 75 57 98 22 49 67 28 94 86 89 60 65 96 11 46 13 23 85 61 9 99 63 52 15 66 40 31 12 72 93 20 77 44 88 55 16 54 38 7 26 19 97 36 14 92 3 4 1 24 2 8 50 76 82 34 51 53 64 45 70 37 18 62 25 21 69 35 74 30 71 84 59 80 83 29 78 68
0 0 ...

output:

195404592

result:

ok 1 number(s): "195404592"

Test #19:

score: 0
Accepted
time: 17ms
memory: 13404kb

input:

100
80 78 96 22 39 21 74 48 61 16 55 32 27 52 34 51 98 4 72 47 42 46 28 90 43 33 44 99 91 11 29 85 92 19 58 73 65 12 87 97 54 59 75 15 9 63 24 67 71 84 36 6 60 94 82 89 70 95 31 5 10 3 37 49 45 18 83 53 64 17 100 1 81 86 88 38 20 40 66 77 50 7 30 69 14 13 79 35 23 68 57 25 8 93 41 62 56 2 76 26
0 48...

output:

119407737

result:

ok 1 number(s): "119407737"

Test #20:

score: 0
Accepted
time: 8ms
memory: 13400kb

input:

100
73 72 15 88 11 48 18 17 52 10 75 99 71 80 97 57 47 32 31 12 64 45 85 26 41 14 21 66 27 84 82 6 29 38 37 62 91 65 92 3 40 1 4 13 42 63 44 68 67 46 87 5 9 50 93 36 7 51 79 58 98 70 56 81 83 96 35 54 74 20 55 2 49 43 59 53 30 94 16 89 19 39 61 22 77 23 90 28 34 8 78 100 76 24 33 69 95 25 60 86
0 0 ...

output:

916702910

result:

ok 1 number(s): "916702910"

Test #21:

score: 0
Accepted
time: 13ms
memory: 13440kb

input:

100
53 38 68 92 52 62 98 90 50 29 20 56 69 89 85 66 12 13 4 57 34 88 73 32 22 44 26 7 55 2 75 6 21 96 25 46 28 58 40 72 19 24 59 37 91 63 10 77 84 3 67 14 9 70 93 97 48 17 80 43 27 100 35 87 8 95 83 33 47 54 18 65 78 36 60 30 23 42 79 15 86 71 1 41 49 64 39 16 31 82 45 5 81 76 99 51 74 94 11 61
0 0 ...

output:

379434745

result:

ok 1 number(s): "379434745"

Test #22:

score: 0
Accepted
time: 13ms
memory: 13632kb

input:

100
96 67 6 71 66 85 72 38 11 47 13 59 17 40 58 39 7 48 28 95 53 42 49 19 33 64 68 5 84 51 97 12 18 43 76 44 89 27 62 88 4 65 74 79 32 70 25 3 20 23 60 98 50 91 26 93 54 21 31 45 73 92 10 29 14 82 37 83 16 77 90 80 56 75 24 61 63 55 99 57 78 9 100 87 41 36 69 30 86 15 22 2 35 81 34 52 94 1 8 46
0 0 ...

output:

831372413

result:

ok 1 number(s): "831372413"

Test #23:

score: 0
Accepted
time: 15ms
memory: 13404kb

input:

100
28 4 61 67 32 97 47 10 53 87 46 35 33 54 45 48 1 77 75 52 8 81 42 14 9 44 92 94 26 43 74 3 50 55 18 40 49 80 70 25 56 98 82 90 69 13 31 84 6 68 34 57 100 39 5 38 93 12 20 89 21 91 99 96 58 78 2 16 83 71 41 95 62 37 7 59 24 60 86 19 22 85 17 23 15 27 73 29 64 63 72 51 88 30 66 79 11 65 76 36
30 3...

output:

842694516

result:

ok 1 number(s): "842694516"

Test #24:

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

input:

100
9 33 80 5 79 68 56 12 17 3 58 39 1 48 76 52 23 74 38 15 82 87 51 78 34 95 26 72 60 64 96 61 43 7 36 44 25 18 75 77 62 22 70 86 50 20 99 73 45 55 66 94 49 90 57 37 53 93 16 24 13 46 6 41 63 71 84 67 54 91 83 8 85 100 88 29 32 81 31 47 42 69 35 89 92 65 98 21 10 2 27 19 40 4 14 30 11 28 97 59
0 0 ...

output:

982762140

result:

ok 1 number(s): "982762140"

Test #25:

score: 0
Accepted
time: 17ms
memory: 13364kb

input:

100
19 55 91 50 31 23 60 84 38 1 22 51 27 76 28 98 11 44 61 63 15 93 52 3 66 16 53 36 18 62 35 85 78 37 73 64 87 74 46 26 82 69 49 33 83 89 56 67 71 25 39 94 96 17 21 6 47 68 34 42 57 81 13 10 54 2 48 80 20 77 4 5 59 30 90 95 45 75 8 88 24 41 40 14 97 32 7 9 65 70 100 99 72 58 92 29 79 12 86 43
0 0 ...

output:

66690913

result:

ok 1 number(s): "66690913"

Test #26:

score: 0
Accepted
time: 16ms
memory: 13464kb

input:

100
38 39 59 95 16 6 33 55 11 10 100 43 77 52 34 1 90 5 37 24 28 22 35 63 71 49 97 79 19 54 21 85 56 13 40 17 57 76 91 99 53 88 20 29 65 81 94 96 89 47 30 80 84 58 9 31 51 61 42 60 73 23 4 74 3 78 8 67 86 14 87 66 2 45 26 70 48 46 72 44 82 69 27 12 92 36 50 62 41 64 75 7 98 15 25 68 18 32 83 93
0 0 ...

output:

899036040

result:

ok 1 number(s): "899036040"

Test #27:

score: 0
Accepted
time: 8ms
memory: 13404kb

input:

100
17 97 68 44 14 16 38 4 29 52 55 93 62 34 96 41 80 40 66 71 47 81 85 99 57 73 5 39 53 9 70 24 86 49 77 50 54 13 7 21 83 25 3 23 42 10 91 79 67 35 92 12 95 26 48 56 27 30 88 1 8 69 20 15 2 76 72 31 19 94 11 89 61 64 28 60 59 18 37 100 63 75 98 36 78 51 22 82 84 32 65 74 46 58 33 43 45 87 6 90
0 0 ...

output:

517437875

result:

ok 1 number(s): "517437875"

Test #28:

score: 0
Accepted
time: 12ms
memory: 13436kb

input:

100
90 100 46 75 59 41 89 99 95 35 5 11 93 85 24 92 87 47 26 4 64 63 70 37 25 39 68 57 52 98 31 45 40 82 30 28 36 19 83 12 21 29 97 54 14 96 43 73 72 49 10 17 33 2 44 91 7 77 78 3 23 80 56 34 22 13 79 27 48 32 15 65 50 60 86 53 88 9 20 42 38 18 74 66 55 6 76 58 84 67 61 71 81 94 69 62 16 51 8 1
0 83...

output:

958635644

result:

ok 1 number(s): "958635644"

Test #29:

score: 0
Accepted
time: 3ms
memory: 13464kb

input:

100
26 67 2 42 77 85 88 49 45 50 71 82 73 96 62 93 78 97 12 34 35 92 94 61 69 74 31 70 87 89 86 10 79 58 3 1 59 41 30 16 83 4 23 25 76 20 75 40 65 68 54 5 6 51 32 64 13 95 21 24 39 66 43 91 18 47 22 15 81 56 100 57 19 98 80 9 53 28 46 37 52 14 27 11 33 29 55 48 36 7 90 63 99 44 60 17 38 8 72 84
63 1...

output:

735454002

result:

ok 1 number(s): "735454002"

Test #30:

score: 0
Accepted
time: 8ms
memory: 13372kb

input:

100
30 14 58 67 48 84 15 16 26 35 47 19 74 9 95 93 60 34 1 98 52 50 63 88 8 64 28 77 25 40 6 55 4 24 73 27 90 31 45 2 80 87 23 10 3 53 94 51 62 56 7 78 89 36 12 13 42 57 5 46 81 29 22 18 49 61 75 59 37 82 39 91 76 86 32 20 99 65 66 92 43 85 21 68 72 44 83 38 79 97 54 69 100 71 11 41 33 70 96 17
45 2...

output:

477087154

result:

ok 1 number(s): "477087154"

Test #31:

score: 0
Accepted
time: 16ms
memory: 13700kb

input:

100
2 4 82 12 47 63 52 91 87 45 53 1 17 25 64 50 9 13 22 54 21 30 43 24 38 33 68 11 41 78 99 23 28 18 58 67 79 10 71 56 49 61 26 29 59 20 90 74 5 75 89 8 39 95 72 42 66 98 44 32 88 35 92 3 97 55 65 51 77 27 81 76 84 69 73 85 19 46 62 100 60 37 7 36 57 6 14 83 40 48 16 70 96 15 31 93 80 86 94 34
0 37...

output:

316550008

result:

ok 1 number(s): "316550008"

Test #32:

score: 0
Accepted
time: 3ms
memory: 13396kb

input:

100
45 56 48 36 81 10 94 70 86 92 90 1 82 2 5 31 17 98 57 53 100 14 16 55 11 59 61 39 77 44 26 65 79 46 66 21 40 23 64 72 76 38 58 30 71 74 52 20 47 78 18 49 68 8 91 60 12 15 87 4 89 19 13 80 42 96 32 63 67 37 84 7 6 24 34 85 54 83 93 50 3 97 51 43 35 29 27 25 99 75 28 95 9 41 33 69 22 88 73 62
71 8...

output:

104300725

result:

ok 1 number(s): "104300725"

Test #33:

score: 0
Accepted
time: 3ms
memory: 13464kb

input:

100
70 5 29 43 3 84 78 68 64 73 31 49 18 69 60 92 48 15 35 58 13 90 22 66 12 55 8 27 14 80 94 65 96 74 10 88 23 38 41 44 25 52 19 47 26 45 11 28 95 9 86 77 79 37 4 61 97 51 59 6 53 98 91 24 33 46 50 85 76 67 34 30 99 2 36 32 62 72 93 75 21 71 63 89 56 16 83 54 57 1 100 39 87 17 40 42 7 81 82 20
87 8...

output:

131305690

result:

ok 1 number(s): "131305690"

Test #34:

score: 0
Accepted
time: 3ms
memory: 13456kb

input:

100
97 23 19 13 87 95 35 46 98 6 1 100 66 39 48 86 51 89 67 49 76 22 21 62 61 84 29 9 41 69 16 68 30 65 7 36 4 52 25 24 47 55 80 64 5 58 28 82 53 20 57 26 88 94 43 44 99 45 85 42 2 72 70 15 60 50 27 59 56 32 17 91 92 33 18 77 74 54 14 93 63 73 78 40 90 3 71 81 8 10 79 75 83 11 38 96 12 31 34 37
83 1...

output:

121844310

result:

ok 1 number(s): "121844310"

Test #35:

score: 0
Accepted
time: 9ms
memory: 13476kb

input:

100
78 66 37 31 84 90 17 80 40 14 1 38 79 64 26 34 87 75 3 41 67 77 58 6 50 82 8 81 27 9 13 22 16 52 42 65 53 46 92 44 99 18 11 33 55 45 23 21 76 85 48 56 98 61 95 70 62 86 39 43 57 15 47 96 32 60 10 24 5 73 88 30 97 4 35 12 29 94 83 91 93 100 51 2 54 19 20 71 28 69 74 7 72 59 68 25 49 63 89 36
22 3...

output:

18919311

result:

ok 1 number(s): "18919311"

Test #36:

score: 0
Accepted
time: 4ms
memory: 13664kb

input:

100
88 31 100 15 92 44 94 22 24 51 95 41 30 86 34 37 38 12 4 81 60 69 45 40 99 62 6 46 35 27 96 36 59 47 73 78 65 87 3 9 85 57 2 77 26 20 55 97 64 58 63 21 80 19 42 54 49 79 66 70 75 17 16 13 89 28 72 48 90 74 61 71 1 23 5 76 43 32 29 83 18 93 8 7 14 10 39 91 50 67 82 53 52 11 68 33 98 25 84 56
18 8...

output:

8454871

result:

ok 1 number(s): "8454871"

Test #37:

score: 0
Accepted
time: 6ms
memory: 13464kb

input:

100
70 54 10 72 81 84 56 15 27 19 43 100 49 44 52 33 63 40 95 17 58 2 51 39 22 18 82 1 16 99 32 29 24 94 9 98 5 37 47 14 42 73 41 31 79 64 12 6 53 26 68 67 89 13 90 4 21 93 46 74 75 88 66 57 23 7 25 48 92 62 30 8 50 61 38 87 71 34 97 28 80 11 60 91 3 35 86 96 36 20 59 65 83 45 76 77 78 69 85 55
29 7...

output:

42741099

result:

ok 1 number(s): "42741099"