QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #61373 | #1083. Belarusian State University | grass8cow | WA | 3ms | 7840kb | C++14 | 1.8kb | 2022-11-12 18:18:27 | 2022-11-12 18:18:28 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,c[18][2][2],A[18],T[18],B[18];
char S[4];
void sw(__int128 *a,int i,int ty){
if(ty==0)for(int p=0;p<(1<<n);p++)if((p>>i)&1)a[p^(1<<i)]+=a[p],a[p]=0;
if(ty==1)for(int p=0;p<(1<<n);p++)if((p>>i)&1)a[p]+=a[p^(1<<i)],a[p^(1<<i)]=0;
if(ty==2)for(int p=0;p<(1<<n);p++)if((p>>i)&1)swap(a[p],a[p^(1<<i)]);
}
__int128 a[1<<18],b[1<<18],ans[1<<18];
void FWT(__int128 *a,int fl){
for(int w=0;w<n;w++){
int o=(1<<(fl?w:(n-1-w)));
for(int i=0;i<(1<<n);i+=(o<<1))for(int j=0;j<o;j++){
if(!T[w]){
if(fl)a[i+j]+=a[i+j+o];
else a[i+j]-=a[i+j+o];
}
else{
__int128 x=a[i+j],y=a[i+j+o];
a[i+j]=x+y,a[i+j+o]=x-y;
if(!fl)a[i+j]/=2,a[i+j+o]/=2;
}
}
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s",S);
for(int j=0;j<2;j++)for(int k=0;k<2;k++)c[i][j][k]=S[2*j+k]-'0',A[i]+=c[i][j][k];
}
for(int i=0,x;i<(1<<n);i++)scanf("%d",&x),a[i]=x;
for(int i=0,x;i<(1<<n);i++)scanf("%d",&x),b[i]=x;
for(int i=0;i<n;i++){
if(A[i]==1||A[i]==3){
for(int j=0;j<2;j++)for(int k=0;k<2;k++)if(c[i][j][k]&&A[i]==1||!c[i][j][k]&&A[i]==3){
if(!j)sw(a,i,2);
if(!k)sw(b,i,2);
}
if(A[i]==3)B[i]=1;
}
if(A[i]==2){
if(c[i][1][0]&&c[i][0][1]){T[i]=1;continue;}
if(c[i][0][0]&&c[i][1][1]){T[i]=B[i]=1;continue;}
if(c[i][1][0]==c[i][1][1]){
sw(b,i,1);
if(!c[i][1][0])B[i]=1;
}
if(c[i][0][1]==c[i][1][1]){
sw(a,i,1);
if(!c[i][0][1])B[i]=1;
}
}
}
FWT(a,1),FWT(b,1);
for(int i=0;i<(1<<n);i++)ans[i]=a[i]*b[i];
FWT(ans,0);
for(int i=0;i<n;i++){
if(A[i]==0)sw(ans,i,0);
if(A[i]==4)sw(ans,i,1);
if(B[i])sw(ans,i,2);
}
for(int i=0;i<(1<<n);i++)printf("%lld ",(long long)ans[i]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7700kb
input:
3 0111 0110 0001 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0
output:
0 0 0 0 0 0 0 1
result:
ok 8 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
2 1100 1101 2 0 2 1 2 0 2 1
output:
2 4 3 16
result:
ok 4 number(s): "2 4 3 16"
Test #3:
score: 0
Accepted
time: 3ms
memory: 7704kb
input:
1 0000 142857142 857142857 998244353 1755646
output:
999999998000000001 0
result:
ok 2 number(s): "999999998000000001 0"
Test #4:
score: 0
Accepted
time: 2ms
memory: 7840kb
input:
8 0000 0001 0010 0011 0101 1011 1101 1111 92726 51723 30325 31984 47551 61529 94856 58867 99699 44383 29317 34253 85206 99155 54057 21538 23635 64524 11223 78186 73723 38530 99909 38218 32839 92947 57594 79376 87975 25597 26783 11600 77813 98155 26224 76035 42536 80097 32406 81442 49449 76444 40502 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2008949968122 0 631347707836 0 560922365664 ...
result:
ok 256 numbers
Test #5:
score: -100
Wrong Answer
time: 3ms
memory: 7752kb
input:
9 1011 1011 0111 0110 1000 0000 0001 0100 1011 3 1 3 6 0 3 0 0 2 9 4 4 3 0 4 0 3 2 3 0 0 4 0 0 3 4 0 6 2 2 4 5 0 2 3 3 2 4 4 0 3 1 3 5 3 0 4 4 0 0 5 0 2 1 2 0 3 4 0 4 0 8 3 3 0 4 5 0 2 2 3 4 3 1 1 5 7 0 0 0 2 3 0 2 3 5 0 0 0 4 0 0 2 4 3 2 2 6 0 3 5 2 4 7 5 0 2 5 5 0 6 2 3 0 0 5 1 4 5 8 4 2 3 7 0 4 5...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 262nd numbers differ - expected: '1526976', found: '2483264'