QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#329969#6611. United in StormwindOgiso_SetsunaWA 1ms3616kbC++141.2kb2024-02-17 10:05:322024-02-17 10:05:34

Judging History

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

  • [2024-02-17 10:05:34]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3616kb
  • [2024-02-17 10:05:32]
  • 提交

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;
ll _n,K;
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(){
	cin>>n>>m>>K;
	rep(i,1,n){
		char s[25];
		cin>>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-2) g[i] = f[(n-1)^i]/2;
	g[n-1] = f[0] - _n;
	//puts("");

	//rep(i,0,n-1) cout<<g[i]<<" ";
	//puts("");
	FWT(g,Cand);
	//rep(i,0,n-1) cout<<g[i]<<" ";
	ll sum = 0;
	rep(i,1,n-1) if(_n*(_n-1)/2-g[i]>=K) sum++;
	cout<<sum;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

2 2 1
AA
BB

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

2 2 1
AA
AB

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3556kb

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:

176

result:

wrong answer 1st numbers differ - expected: '300', found: '176'