QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#27304	#3542. Very Simple Sum	George_Plover^#	AC ✓	963ms	11760kb	C++20	1.7kb	2022-04-09 14:18:12	2022-04-29 05:36:57

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-29 05:36:57]
评测

测评结果：AC
用时：963ms
内存：11760kb

查看

[2022-04-09 14:18:12]
提交

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) % mod, a[i + (1 << dim)] = (x - y + mod) % mod;
            } 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;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 924ms

memory: 10864kb

input:

1
1
1

output:

result:

ok 1 number(s): "1"

Test #2:

score: 0

Accepted

time: 918ms

memory: 10940kb

input:

5
227 67 445 67 213
297 171 324 493 354

output:

result:

ok 1 number(s): "42"

Test #3:

score: 0

Accepted

time: 923ms

memory: 11568kb

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: 11584kb

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: 963ms

memory: 10892kb

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: 916ms

memory: 11400kb

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: 10956kb

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: 910ms

memory: 10972kb

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: 10868kb

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: 910ms

memory: 10924kb

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: 918ms

memory: 11720kb

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: 918ms

memory: 10960kb

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: 916ms

memory: 10916kb

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: 908ms

memory: 10932kb

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: 913ms

memory: 10892kb

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: 912ms

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: 916ms

memory: 11192kb

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: 0

Accepted

time: 913ms

memory: 11032kb

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:

636404192

result:

ok 1 number(s): "636404192"

Test #19:

score: 0

Accepted

time: 916ms

memory: 11052kb

input:

10000
1 22 27 94 89 48 50 96 55 77 74 33 96 48 76 67 9 87 69 81 71 64 94 8 95 20 64 100 2 83 41 68 98 19 17 33 99 37 30 39 87 31 92 27 27 8 54 11 15 59 71 77 98 76 54 9 88 14 10 2 23 55 79 1 66 6 95 62 37 40 73 41 11 100 2 58 21 43 55 17 38 17 73 15 70 98 97 56 82 21 80 3 11 93 88 20 79 63 85 13 67 ...

output:

774907182

result:

ok 1 number(s): "774907182"

Test #20:

score: 0

Accepted

time: 918ms

memory: 11104kb

input:

10000
25 67 72 76 39 25 34 84 15 59 13 85 86 89 3 84 31 49 87 26 19 45 7 91 52 33 77 49 10 54 67 42 1 55 25 41 33 16 71 46 92 46 77 73 15 96 65 51 33 17 84 29 87 100 46 47 75 35 69 6 26 64 14 87 93 67 84 82 36 74 18 23 34 11 77 92 82 26 8 21 89 65 99 39 1 74 57 98 32 40 14 15 23 58 98 15 84 10 19 37...

output:

879052589

result:

ok 1 number(s): "879052589"

Test #21:

score: 0

Accepted

time: 916ms

memory: 11376kb

input:

10000
53 11 30 46 92 97 9 76 70 46 53 29 81 18 22 1 54 99 9 79 68 27 17 71 13 53 94 13 35 24 85 21 88 92 38 37 62 91 9 57 84 56 66 27 4 76 77 91 47 84 98 73 77 24 46 89 62 56 16 22 37 77 49 65 25 32 56 5 31 100 75 6 53 27 45 18 42 9 65 29 35 25 26 67 36 42 33 45 81 59 52 32 30 19 15 9 100 61 61 58 1...

output:

222383782

result:

ok 1 number(s): "222383782"

Test #22:

score: 0

Accepted

time: 910ms

memory: 11040kb

input:

10000
77 63 76 27 54 70 92 60 26 24 1 68 71 60 41 18 68 61 31 24 20 5 26 54 66 61 15 74 47 86 11 87 75 24 47 49 92 62 46 75 85 79 47 86 1 59 88 35 65 43 12 29 66 41 38 24 49 77 71 31 40 90 88 46 56 98 45 37 29 38 20 96 68 39 24 53 98 96 11 45 86 77 64 91 79 6 5 91 23 89 90 40 41 88 20 95 8 13 95 74 ...

output:

977802728

result:

ok 1 number(s): "977802728"

Test #23:

score: 0

Accepted

time: 929ms

memory: 11708kb

input:

100000
92 20 39 95 30 50 19 78 37 50 83 52 8 47 11 99 84 53 67 44 12 71 95 47 21 4 39 62 50 63 4 22 65 43 17 21 97 51 55 27 26 35 98 9 84 9 2 21 61 85 18 75 66 77 44 65 49 6 83 53 34 1 60 62 86 51 58 3 2 17 10 67 18 89 95 42 59 15 11 42 44 45 56 47 10 96 44 4 36 7 10 44 100 63 42 46 32 90 81 76 62 1...

output:

143863540

result:

ok 1 number(s): "143863540"

Test #24:

score: 0

Accepted

time: 923ms

memory: 11736kb

input:

100000
16 60 93 73 91 26 95 70 1 36 23 100 98 85 22 16 2 4 93 84 52 49 100 26 82 25 56 27 63 33 26 93 61 79 18 29 31 22 93 37 19 50 83 67 73 97 13 61 75 48 36 15 51 10 40 100 36 31 38 65 41 14 7 40 17 16 47 26 1 51 58 50 37 100 63 72 15 2 64 58 98 1 82 63 53 55 11 47 86 30 47 56 15 28 51 44 48 42 23...

output:

178713544

result:

ok 1 number(s): "178713544"

Test #25:

score: 0

Accepted

time: 937ms

memory: 11760kb

input:

100000
44 5 42 51 49 95 78 58 60 14 66 48 88 18 49 29 25 66 11 29 1 39 10 9 39 33 78 76 79 4 44 71 52 12 27 33 60 89 26 52 24 64 68 22 70 68 25 5 93 10 50 71 40 26 32 38 27 52 93 73 57 27 42 18 52 81 28 50 96 77 11 40 60 8 42 6 76 89 21 66 49 61 21 91 88 31 75 93 35 49 81 61 27 93 60 34 56 89 57 17 ...

output:

641634039

result:

ok 1 number(s): "641634039"

Test #26:

score: 0

Accepted

time: 930ms

memory: 11724kb

input:

100000
68 49 96 32 98 68 61 46 15 96 2 87 82 55 68 46 47 16 33 82 53 17 23 89 96 41 99 41 95 78 71 42 39 48 40 37 90 60 68 63 17 82 53 76 58 52 36 45 19 73 68 27 29 50 28 73 18 73 36 77 60 33 77 8 83 43 9 82 95 11 60 22 75 20 17 32 36 68 66 82 96 13 47 10 19 99 47 40 77 68 19 77 26 58 69 29 73 36 3 ...

output:

767591848

result:

ok 1 number(s): "767591848"

Test #27:

score: 0

Accepted

time: 936ms

memory: 11712kb

input:

100000
92 97 46 2 60 45 36 34 71 83 46 31 73 88 87 64 66 78 51 27 94 94 40 72 57 61 16 2 12 48 1 20 38 81 53 42 24 39 6 69 10 97 38 27 55 39 48 85 33 36 77 66 19 75 24 15 5 94 95 94 63 54 16 85 6 100 98 1 86 49 5 9 94 31 85 67 88 55 19 86 46 69 73 34 62 63 23 86 31 98 57 94 37 23 87 19 81 96 45 53 5...

output:

892026304

result:

ok 1 number(s): "892026304"

Test #28:

score: 0

Accepted

time: 921ms

memory: 11664kb

input:

100000
331 189 193 359 300 308 73 248 186 178 432 261 320 358 450 100 274 350 331 226 69 331 302 353 144 307 93 360 340 29 75 42 49 320 120 251 430 441 309 386 205 104 181 269 176 31 289 49 497 380 481 347 452 206 317 463 380 291 181 477 357 489 105 363 161 392 78 485 66 370 131 65 469 207 313 139 6...

output:

278716273

result:

ok 1 number(s): "278716273"

Test #29:

score: 0

Accepted

time: 919ms

memory: 11640kb

input:

100000
459 33 246 336 54 381 260 440 46 360 372 4 410 87 261 221 393 112 349 467 318 109 323 32 397 15 110 413 164 399 301 121 136 253 421 456 56 16 250 293 497 15 166 416 365 319 305 89 423 334 403 103 45 38 317 198 471 104 36 293 369 94 236 141 396 449 259 108 357 4 180 455 188 423 188 377 223 132...

output:

313532445

result:

ok 1 number(s): "313532445"

Test #30:

score: 0

Accepted

time: 931ms

memory: 11660kb

input:

100000
179 378 196 18 116 158 231 428 201 246 311 248 309 328 288 330 115 362 367 220 66 387 332 415 254 427 331 478 477 66 323 391 235 389 234 260 286 79 284 7 494 437 447 74 258 403 412 333 41 301 17 347 330 358 213 444 357 225 379 97 276 211 275 227 119 315 340 232 456 238 24 445 204 127 64 307 1...

output:

265253308

result:

ok 1 number(s): "265253308"

Test #31:

score: 0

Accepted

time: 940ms

memory: 11712kb

input:

100000
307 18 250 187 369 127 419 416 357 225 455 299 399 58 407 247 30 421 89 460 7 472 342 94 315 147 53 135 85 436 241 266 26 129 343 464 15 154 21 414 95 348 228 233 254 474 224 373 455 460 131 398 319 487 109 178 448 346 439 402 287 20 111 4 150 180 329 356 55 372 381 28 15 138 143 237 31 2 434...

output:

68747756

result:

ok 1 number(s): "68747756"

Test #32:

score: 0

Accepted

time: 936ms

memory: 11760kb

input:

100000
231 362 199 369 123 200 94 404 420 407 203 339 489 491 422 165 252 171 311 201 459 46 455 170 172 356 70 188 205 306 467 240 113 266 143 64 245 229 463 25 388 462 317 187 443 262 35 413 73 426 448 450 209 307 5 117 39 467 294 410 491 137 150 486 385 137 306 479 346 6 226 110 234 354 210 372 4...

output:

231738288

result:

ok 1 number(s): "231738288"

Test #33:

score: 0

Accepted

time: 923ms

memory: 11708kb

input:

100000
492 500 491 489 494 490 484 488 495 484 486 492 485 499 484 498 487 489 500 493 499 499 488 492 488 489 487 483 500 491 488 499 485 491 489 485 485 496 484 483 488 487 485 499 495 484 492 483 493 496 491 483 487 484 490 486 493 491 499 491 490 493 495 491 498 495 496 493 488 488 493 485 498 4...

output:

736020263

result:

ok 1 number(s): "736020263"

Test #34:

score: 0

Accepted

time: 926ms

memory: 11724kb

input:

100000
496 490 493 491 489 498 499 498 496 493 499 495 483 490 487 487 492 495 498 500 497 491 488 488 493 495 492 494 490 489 488 488 484 493 500 493 494 483 490 500 487 489 490 488 489 490 485 491 497 485 498 492 496 500 500 492 500 494 498 496 496 494 500 486 498 486 485 496 493 494 498 487 498 4...

output:

334641190

result:

ok 1 number(s): "334641190"

Test #35:

score: 0

Accepted

time: 934ms

memory: 11740kb

input:

100000
486 491 485 492 491 485 489 490 498 483 491 495 486 488 490 498 486 497 496 484 486 483 497 487 494 497 483 499 484 498 494 484 489 492 487 493 500 492 485 486 496 484 491 498 484 486 489 499 488 492 488 484 483 490 500 488 485 497 487 496 497 495 489 486 485 499 487 500 498 490 488 487 497 4...

output:

876638994

result:

ok 1 number(s): "876638994"

Test #36:

score: 0

Accepted

time: 923ms

memory: 11668kb

input:

100000
494 495 490 490 492 484 486 500 495 491 486 499 498 493 483 495 491 486 498 487 492 486 488 492 499 500 498 496 497 496 491 490 494 494 488 483 496 497 495 485 491 490 496 491 483 495 500 485 492 498 488 494 489 499 500 491 492 496 498 496 488 496 483 486 484 483 490 486 495 487 483 493 492 4...

output:

69597429

result:

ok 1 number(s): "69597429"

Test #37:

score: 0

Accepted

time: 926ms

memory: 11592kb

input:

100000
498 495 486 491 484 497 493 492 493 499 496 498 486 490 496 492 495 488 488 494 495 496 498 487 486 484 489 489 495 486 487 491 493 493 485 487 484 484 483 490 486 485 491 497 495 491 486 493 492 487 492 486 484 497 496 497 498 499 497 500 489 497 490 496 483 496 493 489 500 497 492 500 491 4...

output:

895027375

result:

ok 1 number(s): "895027375"

Test #38:

score: 0

Accepted

time: 905ms

memory: 10820kb

input:

20
496 485 485 495 496 483 490 489 490 493 496 491 487 487 492 497 487 489 494 496
485 489 484 493 500 500 499 493 484 496 494 488 490 488 487 488 499 492 497 483

output:

632858349

result:

ok 1 number(s): "632858349"

Test #39:

score: 0

Accepted

time: 915ms

memory: 10912kb

input:

20
500 489 494 497 498 495 494 499 488 487 491 491 494 492 495 494 495 500 496 488
483 489 484 489 483 484 486 500 492 486 490 488 485 490 487 492 491 497 497 488

output:

62917734

result:

ok 1 number(s): "62917734"

Test #40:

score: 0

Accepted

time: 915ms

memory: 10956kb

input:

20
494 494 490 486 490 500 495 491 489 495 483 494 488 490 498 491 500 498 486 483
490 499 489 498 488 487 491 483 500 485 486 495 490 489 492 496 483 488 488 500

output:

641490407

result:

ok 1 number(s): "641490407"

Test #41:

score: 0

Accepted

time: 907ms

memory: 11024kb

input:

20
498 494 496 488 491 499 498 483 487 499 497 490 486 499 491 488 490 494 485 486
496 490 484 489 489 493 500 484 499 497 492 487 499 491 485 500 484 485 494 491

output:

351781878

result:

ok 1 number(s): "351781878"

Test #42:

score: 0

Accepted

time: 919ms

memory: 11252kb

input:

20
488 495 491 489 497 494 496 499 488 494 492 494 484 496 490 485 495 492 487 493
491 490 494 488 500 495 487 495 489 487 493 497 494 489 486 486 490 490 489 486

output:

915968356

result:

ok 1 number(s): "915968356"