QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#235873 | #6611. United in Stormwind | whsyhyyh# | TL | 1ms | 5920kb | C++14 | 1.3kb | 2023-11-03 11:42:54 | 2023-11-03 11:42:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
const int N = 2e6+9;
void FWT(ll *f,int n,int flag){
for(int p=2;p<=n;p<<=1){
int len=p>>1;
for(int l=0;l<n;l+=p){
for(int k=l;k<l+len;k++){
ll tt=f[k+len];
f[k+len]=f[k]-tt;
f[k]=f[k]+tt;
}
}
}
if(!flag){
for(int i=0;i<n;i++) f[i]/=n;
}
return ;
}
int n,m,k,a[N];
char s[N];
ll f[N];
signed main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=n;i++){
scanf("%s",s);
for(int j=1;j<=m;j++)
if(s[j-1]=='B') a[i]=(a[i]<<1)|1;
else a[i]=(a[i]<<1);
}
for(int i=1;i<=n;i++) f[a[i]]++;
int len=(1<<m);
FWT(f,len,1);
for(int i=0;i<len;i++) f[i]*=f[i];
FWT(f,len,0);
// for(int i=0;i<len;i++) printf("%lld %lld\n",i,f[i]);
for(int i=1;i<len;i++) f[i]/=2;
for(int i=len-1;i>=0;i--){
for(int j=len-1-i;j;j=(j-1)&(len-1-i)){
int x=j+i;
f[x]+=f[i];
}
}
// for(int i=1;i<len;i++) printf("%lld\n",f[i]);
ll ans=0;
for(int i=1;i<len;i++) if(f[len-1]-f[len-1-i]>=k) ans++;
printf("%lld\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5668kb
input:
2 2 1 AA BB
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5576kb
input:
2 2 1 AA AB
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5740kb
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:
300
result:
ok 1 number(s): "300"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5672kb
input:
5000 10 1 AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABBAABBBB AABB...
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5616kb
input:
5000 10 8968133 BABAAAAAAA BABAAAAAAA AAABAAAAAA BABBBBBAAA AABBAAABAA AAABAAAAAA ABAAABAAAB BABBBBBAAA BABAAAAAAA BABBBBBAAA ABAAABAAAB BABAAAAAAA ABAAABAAAB AABBAAABAA AAABAAAAAA BABAAAAAAA AAABAAAAAA BABBBBBAAA BABBBBBAAA BABAAAAAAA BABAAAAAAA AABBAAABAA AABBAAABAA AAABAAAAAA AAABAAAAAA AAABAAAAA...
output:
886
result:
ok 1 number(s): "886"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5916kb
input:
5000 10 10507302 BBBAABAAAB BBBAABAAAB ABAABAAAAA BBBABBAAAA ABBABABBAB ABBABABBAB BBBABBAAAA BBBABBAAAA AABAABBABA ABBABAAABB ABBABAAABB ABAABAAAAA BBABBABBAB BAABBAABAA BAABBBAAAA BABBBABAAB ABBABAAABB BAABBAABAA BBABBABBAB BBABBABBAB ABAABAAAAA ABBABABBAB ABAABAAAAA ABBABAAABB AABAABBABA BBABBABB...
output:
755
result:
ok 1 number(s): "755"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
5000 10 10810288 BBBAAABBBB BBBBBAAAAB BBBABAABBB BBBBABBBBA BBBBABBBBA AAAAAABAAA BBAAABBABB AAABBABAAB AAABBBAABB ABBBBBABBA ABABABBBBA AABBABBBAA AAABAABBAB BBBAABBBAA AAABAABBAA BBAABBBAAA ABBAABABBB BBAABBBAAA BAABBBBABA BBBBBABABA AABABABAAA BABBBBBAAB BBABBABAAB AAABAABBAA BBBBABBBBA AAABAAAB...
output:
870
result:
ok 1 number(s): "870"
Test #8:
score: 0
Accepted
time: 0ms
memory: 5744kb
input:
5000 10 12280385 ABABAAABBA ABBBBABBAB AABBBBAABA BBBABAABAA AAAAABABAA BBBBABAAAA BBAAAABBBA ABABBABAAB ABABAABBAB BAAABAAAAB AAAABBBABA BABBBAABAA ABBBBBBAAB ABBBABBABA BBAABAABAA ABABBBAABB ABBBBBAAAB BBBAABBAAB BBBBBAABBB BBBABAABAB ABAAAAABBB AAAAABABAA BBAAAAABBA BAAABBABAB BABBBBBABA ABAAABAB...
output:
141
result:
ok 1 number(s): "141"
Test #9:
score: 0
Accepted
time: 1ms
memory: 5920kb
input:
5000 10 12436636 ABABABAABB ABAABAAABA BBBBAAABAB BABAAABAAB BBABABAABB ABAABAAABB ABBAAAABAB BAAAABBBBB ABABAAAABB BAABAAABBA AAAAAAABAA BAAABBABAB BAAABBBABA AAAABBBBAA AABBBAABBA BBBAAAABAB BBBBAABBBB AABABBBBBA ABABBBAABB BBAABBABBA ABAABABABA BBBBAAABAB BBBBBAAAAA AAABABAAAB ABABAAAAAA AABBABAB...
output:
28
result:
ok 1 number(s): "28"
Test #10:
score: 0
Accepted
time: 0ms
memory: 5696kb
input:
5000 10 9373047 ABABAAABBB BABBAABABB ABABAAAAAB ABBBAAAABA ABBBAABABB AABBBBBABB AAABAAABAB ABAABBBBAB ABAAAABAAB BBABBBBBAA AABAAAAABB BAAAAAAABA BAABBABBBB BABAABABBB ABBBAABABB ABBAAAAABB BABBBABBAB ABAAABABAB AABBBABAAA AAABAAAAAB AABBAABABB BBBBAAAAAB AAABBAABBA ABABABABBB AABBBBBBAB AAABAAABB...
output:
999
result:
ok 1 number(s): "999"
Test #11:
score: -100
Time Limit Exceeded
input:
5000 20 12473302 AAAABBABAABBBABABBAB ABAABAAAABAABBABBABA ABBBAABABABABBBAAAAB BBABABBBAAAAAAABABAA BAABBBBAABBBBABABBBB BABBBABBBAAABABAAABB BAAAABAABBABAABBABBA ABBAABAAABABABBABBBA AABAABABAABAABAABBBA BBBABABAABBAABAAAABA BBBBBABAAABBBBBABBBB BBAAAAAAAAABBABBBABA ABBAAAABABAAAAABBBBB BBAABBABAB...