QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #27297 | #3542. Very Simple Sum | George_Plover# | WA | 955ms | 11620kb | C++20 | 1.6kb | 2022-04-09 14:12:28 | 2022-04-29 05:35:40 |
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 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] = (x + y) / 2, a[i + (1 << dim)] = (x - y) / 2;
}
}
}
}
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: 910ms
memory: 10936kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 907ms
memory: 10964kb
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: 948ms
memory: 11620kb
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: 926ms
memory: 10948kb
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: 955ms
memory: 11116kb
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: 906ms
memory: 10912kb
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: 908ms
memory: 10820kb
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: 909ms
memory: 10892kb
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: 896ms
memory: 10984kb
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: 903ms
memory: 10956kb
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: 925ms
memory: 10944kb
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: 901ms
memory: 10892kb
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: -100
Wrong Answer
time: 914ms
memory: 10896kb
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:
607618753
result:
wrong answer 1st numbers differ - expected: '603293709', found: '607618753'