QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#188000#5019. 整数zlt100 ✓213ms5740kbC++14910b2023-09-25 11:07:052023-09-25 11:07:05

Judging History

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

  • [2023-09-25 11:07:05]
  • 评测
  • 测评结果：100
  • 用时：213ms
  • 内存：5740kb
查看
  • [2023-09-25 11:07:05]
  • 提交

answer

#include <cstdio>
const int maxm = (1 << 18) + 50, mod = 998244353;
long long c[20];
int f[maxm], g[maxm], h[maxm], n, m, b[maxm];
inline void upd(int &x, int y) { ((x += y) >= mod) && (x -= mod); }
inline void FWT(int *a, int op, int d) { for (int k = 1, t = 0; k < m; k <<= 1, ++t) for (int i = 0; i < m; i += (k << 1)) for (int j = 0; j < k; ++j) ((c[t] >> d) & 1) ? upd(a[i + j], op ? a[i + j + k] : mod - a[i + j + k]) : upd(a[i + j + k], op ? a[i + j] : mod - a[i + j]); }
int main() {
	scanf("%d", &n); m = (1 << n); for (int i = 0; i < n; ++i) scanf("%lld", &c[i]); for (int i = 0; i < m; ++i) scanf("%1d", &b[i]); h[0] = 1;
	for (int d = 0; d < 60; ++d) { for (int i = 0; i < m; ++i) f[i] = h[i], g[i] = b[i]; FWT(f, 1, d); FWT(g, 1, d); for (int i = 0; i < m; ++i) f[i] = 1LL * f[i] * g[i] % mod; FWT(f, 0, d); for (int i = 0; i < m; ++i) h[i] = f[i]; }
	printf("%d\n", h[0]);
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
557860450892773247 1006376652976945084
1001

output:

434419861

result:

ok 1 number(s): "434419861"

Test #2:

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

input:

2
1114627670617095929 177024338535020511
1000

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

2
1149393890526355314 1070730158013930700
1001

output:

315168037

result:

ok 1 number(s): "315168037"

Test #4:

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

input:

2
971930549804858302 431201925917048822
1001

output:

713084688

result:

ok 1 number(s): "713084688"

Test #5:

score: 5
Accepted
time: 22ms
memory: 3872kb

input:

15
3 2 1 3 0 3 2 2 3 0 3 3 3 1 1
111100000011100110100011100000100010011010010011011101110110000011100111101101100011111100111010001010010001001111010011000000110110011111000011100100010100011010110000000010011110101111110110110100011101011101011100110000001100110111101001101001010111011000000110010...

output:

919883

result:

ok 1 number(s): "919883"

Test #6:

score: 5
Accepted
time: 203ms
memory: 5740kb

input:

18
3 0 3 2 3 3 3 3 3 3 3 1 3 3 3 3 1 3
101101001111111010001101010111101111110111100111111011010010011000101111101100011100101111101001001010010110011001001110011101011100001100100000100011001110101101110010011011000001001001000000001001010000010100010101010101010001001110100111001001110001101000111...

output:

812380442

result:

ok 1 number(s): "812380442"

Test #7:

score: 5
Accepted
time: 199ms
memory: 5680kb

input:

18
3 2 3 3 3 3 3 3 3 1 1 1 2 3 1 3 3 3
100101100011011110000000100100001001010001001000110011011111000010001110111011111010001011101101010101111111000111000011110001100111100001110100110100010101111100001001110110000000111100110011011011000110001010100110001101011011011101000110001000101101000110000...

output:

609445751

result:

ok 1 number(s): "609445751"

Test #8:

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

input:

9
774618017057897470 1150648813667465147 936044467577552867 540429591977619391 492984435788926911 706491668336975855 1148409108818935103 1152305623476461243 1151646826418395103
101100111100110000011001010001100101011001010001111000000000000001011100001010001011100110010110100001000101101101101001011...

output:

762304370

result:

ok 1 number(s): "762304370"

Test #9:

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

input:

9
864195661015236599 828072363954386938 215046877307787767 125420173910435807 863300627424341495 1125890835854768063 538106264396606431 1008449764986412979 1112933880000274175
1111011011101000110000110000110110111101111110011110001110010111100001010001110110111000101011110011001000101011100011011100...

output:

91522040

result:

ok 1 number(s): "91522040"

Test #10:

score: 5
Accepted
time: 1ms
memory: 3660kb

input:

9
1060294142652751871 270953131468627965 950114304166317032 1023152535943950935 1124721212123772879 1136030244306680786 575888989072637942 576457170017579983 1071468780714196734
10010111011101001111011010000011000000111111000001100001001110001000000000101001001101110110001001111011110111101001000000...

output:

235859607

result:

ok 1 number(s): "235859607"

Test #11:

score: 5
Accepted
time: 1ms
memory: 3620kb

input:

11
1044692707433249934 1008683100277431676 999797431367270367 1143631656501850799 1098790111790735245 468268805647233519 539233207094867537 414313023104679647 1113992177660166126 1150563014851263359 1146149597257104766
111100100001011011010001100111000010001101110011110101110101010110100111111011000...

output:

238088536

result:

ok 1 number(s): "238088536"

Test #12:

score: 5
Accepted
time: 1ms
memory: 3728kb

input:

11
1136928866896019455 954477066817884159 139540257629524991 920699090857753087 852006989960417247 557707207097472255 575228611095427007 1006976729003116287 709142041517850567 1136595818501773047 1006109764096082108
100001110101001011001100010000100000111110011110100011000011111011000001010001110001...

output:

770640307

result:

ok 1 number(s): "770640307"

Test #13:

score: 5
Accepted
time: 1ms
memory: 3608kb

input:

11
1152568556892716543 1152920608551467963 216135265528237819 1116892698712710517 1125524963696923135 990737955748133887 575754796832378359 959086400709851129 571809817905978127 391758946252877613 553053934827077551
100001001101100001010110011000000001110110100101011111010110001101000110111100110011...

output:

12490130

result:

ok 1 number(s): "12490130"

Test #14:

score: 5
Accepted
time: 3ms
memory: 3764kb

input:

13
431747275278769839 792173935971856335 842168688984356222 709201683711004463 1096549254077341383 432312541824942061 423302887995576278 1152284609275166700 1150353045444060639 858881033326555901 429385610205061119 394803803773730111 792573841785221941
11101010110000000010101000000011010001110011111...

output:

711924090

result:

ok 1 number(s): "711924090"

Test #15:

score: 5
Accepted
time: 5ms
memory: 3756kb

input:

13
384952197575497562 925188207794820790 819636358341950664 1008806169945307033 485498962656536575 576170342985224059 1152884825316839167 519602798379984887 1148271257506507710 864338725486642591 141147914734645085 945751520335947454 828363124049108987
10111011110011010100110001011011010100001001111...

output:

17257245

result:

ok 1 number(s): "17257245"

Test #16:

score: 5
Accepted
time: 3ms
memory: 3756kb

input:

13
812148678079544783 531352737042856447 360252648370171639 827797221788122302 1076354330155122647 571657826460300281 995857311985303518 576390067592282047 573059687658290935 1134130623250689782 573953435640528550 1148043723132895167 576443122223672059
11010001100111100001101001010010100111100000010...

output:

513017470

result:

ok 1 number(s): "513017470"

Test #17:

score: 5
Accepted
time: 204ms
memory: 5740kb

input:

18
557601891651940085 863281395625602303 810348831133032447 855679530581929974 1143340273566153982 1142779849869883883 495305789849593903 1141378831228050923 539285017652624765 1151477836095937523 968834653063196607 462735989800959869 567170978455011071 936570564589289083 1089862139502785535 1274543...

output:

905600077

result:

ok 1 number(s): "905600077"

Test #18:

score: 5
Accepted
time: 212ms
memory: 5648kb

input:

18
35461063007254983 250722149174607860 990787107658114938 521176448595639215 1142533318210222071 848423510290851199 936184673027902967 1035761934176939767 1152921455940040799 759980081052254206 841582125096893943 1105339004669119437 1071810531808477044 1072419334446896991 1152903339507575642 131161...

output:

946673491

result:

ok 1 number(s): "946673491"

Test #19:

score: 5
Accepted
time: 201ms
memory: 5716kb

input:

18
526745011001725941 995280101634205694 1150650377238908861 1152780629645981351 378291368993988607 754341611678006135 1133780828220553215 467476844077883365 998548842292821951 1125758065340935934 1074758391215161343 359069688757419477 863137999561424871 459006511440394231 856772308259666431 2832407...

output:

333911712

result:

ok 1 number(s): "333911712"

Test #20:

score: 5
Accepted
time: 213ms
memory: 5712kb

input:

18
1116852845721419519 564031047050710929 1152918474977164029 288041155646291455 647954749928207825 978368260719998815 1141854864204889983 1121382897240509261 576459613035256827 1134273717606465523 1124121994315404271 714513083207720351 1001083345502337005 642993847483219627 1143878547027000662 1139...

output:

437797272

result:

ok 1 number(s): "437797272"
English 繁體中文 简体中文

Server Time: 2024-11-29 06:31:57 | OpenSource Project