QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#62281	#5019. 整数	lmeowdn	10	42ms	76832kb	C++17	1.4kb	2022-11-17 20:28:41	2022-11-17 20:28:44

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-11-17 20:28:44]
评测

测评结果：10
用时：42ms
内存：76832kb

查看

[2022-11-17 20:28:41]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define eb emplace_back
#define fi first
#define se second
#define pc __builtin_popcount
typedef pair<int,int> pii;
typedef vector<int> vi;

int read() {
	int res=0, w=1; char c=getchar();
	while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)) {res=res*10+c-'0'; c=getchar();}
	return res*w;
}

const int mod=998244353,M=19,W=64,N=(1<<M),H=60;

int n,r[W][N],f[W][N],g[W][N],S,ans;
long long rs[N];
char c[N];

void pls(int &x,int y) {x+=y; if(x>=mod) x-=mod;}
void mns(int &x,int y) {x-=y; if(x<0) x+=mod;}
void fwt(int *f,int *g,int *r) {
	for(int i=1,c=0;i<=S;i<<=1,++c)
		for(int j=0;j<=S;j+=(i<<1))
			rep(k,0,i-1) {
				if(r[c]) pls(f[j+k],f[i+j+k]), pls(g[j+k],g[i+j+k]);
				else swap(g[j+k],g[i+j+k]), pls(g[j+k],g[i+j+k]);
			}
}
void ifwt(int *f,int *r) {
	for(int i=1,c=0;i<=S;i<<=1,++c) 
		for(int j=0;j<=S;j+=(i<<1))
			rep(k,0,i-1) if(r[c]) mns(f[j+k],f[i+j+k]);
}

signed main() {
	n=read(); S=(1<<n)-1;
	rep(i,0,n-1) {
		rs[i]=read();
		rep(h,0,H) r[h][i]=(bool)((1ll<<h)&rs[i]);
	}
	scanf("%s",c);
	f[H][S]=1;
	per(i,H-1,0) {
		rep(j,0,S) g[i][j]=c[j]-'0';
		fwt(f[i+1],g[i],r[i]);
		rep(j,0,S) f[i][j]=1ll*f[i+1][j]*g[i][j]%mod;
		ifwt(f[i],r[i]);
	}
	rep(j,0,S) pls(ans,f[0][j]);
	printf("%d\n",ans);
	return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0

Wrong Answer

time: 0ms

memory: 65680kb

input:

2
557860450892773247 1006376652976945084
1001

output:

39638845

result:

wrong answer 1st numbers differ - expected: '434419861', found: '39638845'

Test #2:

score: 5

Accepted

time: 2ms

memory: 65536kb

input:

2
1114627670617095929 177024338535020511
1000

output:

result:

ok 1 number(s): "1"

Test #3:

score: 0

Wrong Answer

time: 2ms

memory: 63500kb

input:

2
1149393890526355314 1070730158013930700
1001

output:

475258738

result:

wrong answer 1st numbers differ - expected: '315168037', found: '475258738'

Test #4:

score: 0

Wrong Answer

time: 2ms

memory: 63504kb

input:

2
971930549804858302 431201925917048822
1001

output:

142080957

result:

wrong answer 1st numbers differ - expected: '713084688', found: '142080957'

Test #5:

score: 5

Accepted

time: 42ms

memory: 76832kb

input:

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

output:

result:

ok 1 number(s): "919883"

Test #6:

score: 0

Memory Limit Exceeded

input:

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

output:

result:

Test #7:

score: 0

Memory Limit Exceeded

input:

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

output:

result:

Test #8:

score: 0

Wrong Answer

time: 0ms

memory: 59476kb

input:

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

output:

76182011

result:

wrong answer 1st numbers differ - expected: '762304370', found: '76182011'

Test #9:

score: 0

Wrong Answer

time: 4ms

memory: 59420kb

input:

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

output:

119949980

result:

wrong answer 1st numbers differ - expected: '91522040', found: '119949980'

Test #10:

score: 0

Wrong Answer

time: 2ms

memory: 59400kb

input:

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

output:

103999357

result:

wrong answer 1st numbers differ - expected: '235859607', found: '103999357'

Test #11:

score: 0

Wrong Answer

time: 4ms

memory: 60344kb

input:

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

output:

515768237

result:

wrong answer 1st numbers differ - expected: '238088536', found: '515768237'

Test #12:

score: 0

Wrong Answer

time: 8ms

memory: 60376kb

input:

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

output:

844707474

result:

wrong answer 1st numbers differ - expected: '770640307', found: '844707474'

Test #13:

score: 0

Wrong Answer

time: 4ms

memory: 60604kb

input:

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

output:

747726917

result:

wrong answer 1st numbers differ - expected: '12490130', found: '747726917'

Test #14:

score: 0

Wrong Answer

time: 17ms

memory: 65376kb

input:

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

output:

595234824

result:

wrong answer 1st numbers differ - expected: '711924090', found: '595234824'

Test #15:

score: 0

Wrong Answer

time: 17ms

memory: 65324kb

input:

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

output:

667022664

result:

wrong answer 1st numbers differ - expected: '17257245', found: '667022664'

Test #16:

score: 0

Wrong Answer

time: 8ms

memory: 65440kb

input:

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

output:

100741672

result:

wrong answer 1st numbers differ - expected: '513017470', found: '100741672'

Test #17:

score: 0

Memory Limit Exceeded

input:

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

output:

result:

Test #18:

score: 0

Memory Limit Exceeded

input:

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

output:

result:

Test #19:

score: 0

Memory Limit Exceeded

input:

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

output:

result:

Test #20:

score: 0

Memory Limit Exceeded

input:

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