QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #27300 | #3542. Very Simple Sum | George_Plover# | WA | 1000ms | 11648kb | C++20 | 1.7kb | 2022-04-09 14:15:10 | 2022-04-29 05:36:14 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; --i)
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int inv2 = (mod + 1) / 2;
const int N = 100005;
const int M = 512;
const int inf = 1e9;
int pw(int x, int y) {
int ret = 1;
while (y) {
if (y & 1) ret = 1ll * ret * x % mod;
x = 1ll * x * x % mod;
y >>= 1;
}
return ret;
}
int n;
int a[N], b[N];
int c[M][M], d[M * 2][M], e[M * 4][M];
void fwt(int *a, int dir) {
rep(dim, 0, 8) {
rep(i, 0, 511) {
if (i & (1 << dim)) continue;
int x = a[i], y = a[i + (1 << dim)];
if (dir == 1) {
a[i] = x + y, a[i + (1 << dim)] = x - y;
} else {
a[i] = 1ll * (x + y) * inv2 % mod,
a[i + (1 << dim)] = 1ll * (x - y + mod) * inv2 % mod;
}
}
}
}
int main() {
scanf("%d", &n);
rep(i, 1, n) scanf("%d", &a[i]);
rep(i, 1, n) scanf("%d", &b[i]);
rep(i, 1, n) { c[a[i]][b[i]]++; }
rep(i, 0, 511) { fwt(c[i], 1); }
rep(i, 0, 511) {
rep(j, 0, 511) {
rep(k, 0, 511) {
d[i + j][k] = (d[i + j][k] + 1ll * c[i][k] * c[j][k]) % mod;
}
}
}
rep(i, 0, 1023) {
rep(j, 0, 1023) {
rep(k, 0, 511) {
e[i + j][k] = (e[i + j][k] + 1ll * d[i][k] * d[j][k]) % mod;
}
}
}
rep(i, 0, 2047) { fwt(e[i], -1); }
int ans = 0;
rep(i, 0, 2047) {
rep(j, 0, 511) { ans = (ans + 1ll * e[i][j] * pw(i, j)) % mod; }
}
printf("%d\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 931ms
memory: 10980kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 923ms
memory: 11096kb
input:
5 227 67 445 67 213 297 171 324 493 354
output:
42
result:
ok 1 number(s): "42"
Test #3:
score: 0
Accepted
time: 922ms
memory: 10884kb
input:
20 93 84 58 43 46 90 86 67 86 1 20 69 91 49 5 97 81 61 81 42 60 73 35 61 94 88 53 52 66 3 5 32 14 48 10 32 86 72 52 32
output:
36313816
result:
ok 1 number(s): "36313816"
Test #4:
score: 0
Accepted
time: 921ms
memory: 10984kb
input:
20 17 24 8 24 99 67 57 51 46 87 63 8 85 83 20 10 95 23 99 83 1 51 48 36 51 97 70 13 79 69 35 15 1 84 23 44 16 35 85 42
output:
357580675
result:
ok 1 number(s): "357580675"
Test #5:
score: 0
Accepted
time: 909ms
memory: 11020kb
input:
20 41 72 62 98 49 32 45 39 1 70 3 52 76 20 43 27 22 70 18 28 53 29 58 15 12 5 95 74 99 40 49 85 100 17 28 44 49 10 23 57
output:
173357999
result:
ok 1 number(s): "173357999"
Test #6:
score: 0
Accepted
time: 914ms
memory: 11648kb
input:
20 69 13 15 72 10 13 28 31 57 48 42 4 62 57 66 44 36 32 40 77 2 15 67 99 69 29 16 27 11 10 75 59 91 49 33 48 79 85 64 64
output:
649835489
result:
ok 1 number(s): "649835489"
Test #7:
score: 0
Accepted
time: 914ms
memory: 11024kb
input:
20 97 65 65 49 64 90 3 15 12 34 90 47 56 94 81 61 63 90 62 21 42 92 76 82 30 37 33 88 20 76 1 30 78 81 41 53 9 55 2 74
output:
304078125
result:
ok 1 number(s): "304078125"
Test #8:
score: 0
Accepted
time: 911ms
memory: 11328kb
input:
100 16 97 48 43 62 18 55 65 37 3 49 84 31 35 20 87 65 4 42 24 77 66 61 70 85 2 1 64 66 4 17 75 47 53 10 40 63 77 94 75 86 90 78 97 72 71 49 63 100 42 55 61 91 63 91 88 7 11 25 76 8 13 80 3 86 32 37 28 73 40 59 33 44 4 53 61 23 62 27 3 21 43 69 5 46 39 94 5 57 86 82 92 35 26 81 6 15 55 30 19 33 13 4 ...
output:
391854458
result:
ok 1 number(s): "391854458"
Test #9:
score: 0
Accepted
time: 913ms
memory: 11584kb
input:
100 36 41 6 24 15 95 34 49 93 85 89 24 21 73 39 96 80 55 60 65 18 44 66 53 42 10 22 29 79 70 43 54 34 89 23 44 93 52 32 82 75 8 59 51 65 55 60 7 14 97 65 9 80 87 95 23 86 32 80 92 15 23 15 81 22 98 18 51 64 66 3 15 63 20 36 95 75 45 80 19 71 99 95 28 89 3 66 56 7 5 20 4 47 95 86 92 32 6 72 43 14 83 ...
output:
782881333
result:
ok 1 number(s): "782881333"
Test #10:
score: 0
Accepted
time: 909ms
memory: 10860kb
input:
100 64 85 59 2 77 64 13 41 48 68 28 67 23 6 58 13 2 17 79 6 66 30 75 33 3 27 39 82 95 41 57 20 29 22 36 44 22 31 69 93 80 23 44 10 53 38 72 51 32 68 79 60 61 12 87 57 76 57 31 96 19 36 54 63 45 63 3 75 63 100 52 2 78 32 12 25 35 32 33 30 18 48 26 48 24 75 37 98 57 36 58 17 54 56 95 91 40 57 18 56 87...
output:
434198484
result:
ok 1 number(s): "434198484"
Test #11:
score: 0
Accepted
time: 915ms
memory: 11136kb
input:
100 92 30 9 79 30 41 97 25 12 50 68 15 13 43 77 30 17 75 93 58 15 12 97 16 64 39 61 42 11 11 83 94 24 54 32 52 56 2 7 7 72 45 33 64 50 26 83 79 54 22 96 12 58 36 87 3 67 78 82 1 30 49 90 41 76 16 88 99 54 38 9 88 1 35 87 56 83 19 78 42 68 4 52 72 59 43 1 45 2 55 96 33 57 21 16 81 48 1 56 80 52 35 8 ...
output:
234628493
result:
ok 1 number(s): "234628493"
Test #12:
score: 0
Accepted
time: 914ms
memory: 10984kb
input:
100 12 78 63 53 80 18 76 13 67 32 7 59 4 76 96 51 43 29 15 3 63 89 6 87 21 51 82 3 28 81 10 73 11 86 45 52 86 77 48 18 73 56 18 19 39 2 95 23 72 93 6 64 44 60 79 38 54 99 37 17 33 62 25 26 11 82 69 23 53 72 54 74 16 51 55 90 43 2 35 50 23 56 91 96 97 11 77 92 56 73 30 46 68 90 25 75 64 52 98 96 33 1...
output:
561690167
result:
ok 1 number(s): "561690167"
Test #13:
score: 0
Accepted
time: 922ms
memory: 10968kb
input:
1000 6 11 90 9 40 28 25 17 8 36 92 33 93 41 57 33 2 98 59 45 80 48 50 80 3 97 5 60 94 65 75 61 76 8 67 41 59 9 68 34 88 18 93 84 13 26 29 27 50 1 36 30 37 20 25 71 90 63 42 1 67 32 43 32 25 83 40 80 41 96 70 18 61 31 58 37 37 56 86 15 66 3 61 18 1 22 55 24 53 94 91 51 89 26 16 61 35 24 17 61 12 85 5...
output:
603293709
result:
ok 1 number(s): "603293709"
Test #14:
score: 0
Accepted
time: 921ms
memory: 11504kb
input:
1000 34 56 44 86 94 1 1 1 67 22 39 77 92 75 80 42 21 48 77 85 21 26 64 64 60 6 22 21 2 31 97 31 67 40 79 49 89 84 5 45 81 37 78 39 2 9 37 63 68 64 54 82 18 40 21 5 77 88 97 13 78 49 83 9 60 48 29 8 32 30 19 100 76 42 33 68 85 43 39 23 16 60 92 46 36 86 23 70 94 9 29 68 96 91 21 59 51 75 51 85 93 59 ...
output:
82406712
result:
ok 1 number(s): "82406712"
Test #15:
score: 0
Accepted
time: 1000ms
memory: 10908kb
input:
1000 58 4 97 68 56 70 84 93 27 5 83 16 86 12 95 59 47 10 95 38 69 3 73 35 21 14 44 82 22 97 15 9 54 77 84 49 22 59 47 60 86 51 67 97 2 97 60 7 86 27 64 26 15 64 17 40 68 9 56 21 82 59 18 87 84 13 13 27 31 64 64 99 95 58 4 98 41 22 84 35 63 16 18 70 67 58 95 17 44 31 67 84 3 56 30 49 60 22 97 97 67 3...
output:
30095324
result:
ok 1 number(s): "30095324"
Test #16:
score: 0
Accepted
time: 911ms
memory: 10892kb
input:
1000 82 44 43 38 9 47 67 81 82 83 23 68 76 45 18 76 62 73 18 83 18 93 82 18 78 22 61 39 35 76 45 80 49 5 97 54 48 34 84 66 79 66 52 51 91 72 68 51 100 90 81 78 96 89 9 86 58 30 99 25 97 76 53 69 11 75 90 51 30 94 20 81 10 62 80 32 1 9 41 43 13 64 48 90 10 18 59 63 98 58 5 97 15 17 52 43 68 70 31 22 ...
output:
707881863
result:
ok 1 number(s): "707881863"
Test #17:
score: 0
Accepted
time: 908ms
memory: 11020kb
input:
1000 11 89 1 19 67 19 46 69 42 69 66 8 62 82 33 93 84 23 28 28 66 71 92 1 39 42 82 96 55 46 72 58 40 41 98 58 82 5 18 73 67 88 33 6 80 60 79 87 18 52 3 33 86 13 5 20 45 51 54 37 100 89 88 55 46 28 79 75 21 28 65 63 29 73 55 58 57 92 94 58 68 16 75 10 45 94 35 10 47 77 43 17 22 86 61 46 84 21 77 46 1...
output:
26750840
result:
ok 1 number(s): "26750840"
Test #18:
score: -100
Wrong Answer
time: 909ms
memory: 11096kb
input:
10000 73 78 73 17 28 75 67 8 100 99 30 90 10 19 65 58 90 37 46 41 30 86 85 33 38 12 39 39 81 5 27 93 10 83 16 25 69 66 92 20 98 13 11 68 26 25 38 67 1 92 49 25 9 51 58 74 97 89 59 98 7 38 39 23 35 48 6 34 46 6 17 51 100 100 19 24 69 56 6 1 84 60 38 87 27 38 26 5 29 3 46 86 4 28 75 26 63 16 43 97 90 ...
output:
828001161
result:
wrong answer 1st numbers differ - expected: '636404192', found: '828001161'