QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#329940 | #6611. United in Stormwind | Ogiso_Setsuna | WA | 1ms | 5796kb | C++14 | 1.1kb | 2024-02-17 09:47:06 | 2024-02-17 09:47:06 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=(1<<20)+5;
double Cor[2][2]={{1,0},{1,1}},Cand[2][2]={{1,1},{0,1}},Cxor[2][2]={{1,1},{1,-1}},
ICor[2][2]={{1,0},{-1,1}},ICand[2][2]={{1,-1},{0,1}},ICxor[2][2]={{0.5,0.5},{0.5,-0.5}};
int n,m,K,a[N],b[N],_n;
double f[N],g[N];
void FWT(double *f,double c[2][2]){
for(int i=1;i<n;i<<=1)
for(int j=0;j<n;j+=i<<1)
for(int k=j;k<i+j;k++){
long long x=f[k],y=f[k+i];
f[k]=c[0][0]*x+c[0][1]*y;
f[k+i]=c[1][0]*x+c[1][1]*y;
}
}
int main(){
scanf("%d%d%d",&n,&m,&K);
rep(i,1,n){
char s[25];
scanf("%s",s+1);
int w = 0;
rep(i,1,m) w=(w<<1)|(s[i]=='B');
f[w] += 1;
}
_n = n;
n = 1<<m;
FWT(f,Cxor);
rep(i,0,n-1) f[i] = f[i]*f[i];
FWT(f,ICxor);
//rep(i,0,n-1) cout<<f[i]<<" ";
rep(i,0,n-1) g[i] = f[(n-1)^i];
//puts("");
FWT(g,Cand);
//rep(i,0,n-1) cout<<g[i]<<" ";
ll sum = 0;
rep(i,1,n-1) if(_n*_n-g[i]>K) sum++;
cout<<sum;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5740kb
input:
2 2 1 AA BB
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5616kb
input:
2 2 1 AA AB
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 5796kb
input:
5000 10 12302135 AABAAAABBA AAABAABBAB BAABABAAAB ABBAABBBBA BAAAAABAAB BABBAAAAAA BABBABABAB BBABBAAAAB BABBABBBBA AAAAAAABAA BBBBBAABBA BAABABBAAB BABAAABAAA AAAAABAABB BBABAABABB ABAABBABBA BBBAAABABA BAAABABBAB ABAAAAABAA AABBBBBBAA ABBABBABBA AABBBABBAB BAABBAAABB BAAABBBBBB ABABBAABBB BABBABBA...
output:
1023
result:
wrong answer 1st numbers differ - expected: '300', found: '1023'