QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#235873#6611. United in Stormwindwhsyhyyh#TL 1ms5920kbC++141.3kb2023-11-03 11:42:542023-11-03 11:42:54

Judging History

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

  • [2023-11-03 11:42:54]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:5920kb
  • [2023-11-03 11:42:54]
  • 提交

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...

output:


result: