QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#353106#1287. Anti-hash TestDiuWA 1ms6000kbC++142.5kb2024-03-13 21:14:472024-03-13 21:14:47

Judging History

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

  • [2024-03-13 21:14:47]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6000kb
  • [2024-03-13 21:14:47]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10,mod=1e9+7,inv2=mod+1>>1,inv3=(mod+1)/3;
int T;
ll n;
int a[N],b[N];
char s[N];
int qpow(int x,ll y=mod-2){
	int m=1;y%=(mod-1);
	for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)m=1ll*m*x%mod;
	return m;
}
int f[30],g[30];
const int ff[]={0,3,6,23,86,344,1376,5504,22016,88064,352256,1409024,5636096,22544384,90177536,360710144,442840569,771362269,85449055,341796220,367184873,468739485,627755651,874957933};
void init(int n){
	for(int i=1;i<=n;i++)f[i]=(2*f[i-1]+(i&1^1))%mod;
	for(int i=1;i<=n;i++)g[i]=2*(g[i-1]+1)%mod;
}
int calc(int x){//求出出现恰好一次的本质不同子串数量 
	return ff[x];
}
void work(ll k,int n,bool x,int c){
//	printf("%lld %d %d %d\n",k,n,x,c);
	if(k<0||n>=5){puts("-1");return;}
	if(n==4)n-=2,k-=2,c+=2,x^=1;
	if(n==1){
		int ans=2ll*(f[c]+1)*(f[c]+1)%mod;
		if(k==0){
			if(x==1)puts("-1");
			else printf("1 %d\n",calc(c));
		}else if(k==1)printf("1 %d\n",calc(k+c));
		else{
			printf("%d %d\n",qpow(2,k-1),ans);
		}
		return;
	}
	if(n==2){
		int ans=1ll*(f[c+1]+1)*(f[c+1]+1)%mod;
		if(k==0)puts("-1");
		else if(k==1){
			if(x==1)puts("-1");
			else printf("1 %d\n",calc(k+c));
		}else if(k==2){
			printf("1 %d\n",calc(k+c));
		}else if(k&1){
			int val=1ll*(qpow(2,k+1)-1)*inv3%mod;
			val=1ll*(val+1)*inv2%mod;
			if(x)val=(val-x+mod)%mod;
			if(x&&c)ans=(ans+2)%mod;
			printf("%d %d\n",val,ans);
		}else{
			int val=1ll*(qpow(2,k)-1)*inv3%mod;
			ans=1ll*ans*2%mod;
			if(!x&&c)ans=(ans+2)%mod;
			printf("%d %d\n",val,ans);
		}
		return;
	}
	if(n==3){
		k-=2;
		if(k<=0)puts("-1");
		else if(k==1){
			printf("1 %d\n",calc(k+c+2));//求出出现恰好一次的本质不同子串数量 
		}else{
			int val=1ll*(qpow(2,k+(k&1))-1)*inv3%mod;
			if(k&1^1)val=2ll*val%mod;
			printf("%d %d\n",val,calc(c+2));
		}
		return;
	}
	puts("-1");
}
void solve(ll k,int n){
	int c=0;
	while(1){
		int i=2;
		while(i<=n&&a[i]!=a[i-1])++i;
		if(i>n)return work(k,n,a[1],c);
		if(i&1){
			for(int j=1;j<=n;j+=2){
				if(j<n&&a[j]==a[j+1]){puts("-1");return;}
				a[j+1>>1]=a[j];
			}
			n=n+1>>1;
		}else{
			a[0]=a[1]^1;
			for(int j=0;j<=n;j+=2){
				if(j<n&&a[j]==a[j+1]){puts("-1");return;}
				a[j+2>>1]=a[j];
			}
			n=n+2>>1;
		}
		--k,++c;
	}
}
signed main(){
	scanf("%d",&T);
	init(25);
	for(;T--;){
		scanf("%lld\n%s",&n,s+1);
		int len=strlen(s+1);
		for(int i=1;i<=len;i++)a[i]=s[i]=='b';
		solve(n,len);
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5816kb

input:

4
10
a
10
abba
5
abbabaabbaababbabaababbaabbabaab
20
ababab

output:

512 2
171 4
1 344
-1

result:

ok 7 tokens

Test #2:

score: 0
Accepted
time: 1ms
memory: 5872kb

input:

3
1
a
1
ab
1
b

output:

1 3
1 3
1 3

result:

ok 6 tokens

Test #3:

score: 0
Accepted
time: 1ms
memory: 6000kb

input:

10
2
a
2
ab
2
abb
2
abba
2
b
2
bb
2
bba
2
b
2
ba
2
a

output:

2 2
1 6
1 6
1 6
2 2
1 6
1 6
2 2
1 6
2 2

result:

ok 20 tokens

Test #4:

score: 0
Accepted
time: 1ms
memory: 5996kb

input:

36
3
a
3
ab
3
abb
3
abba
3
abbab
3
abbaba
3
abbabaa
3
abbabaab
3
b
3
bb
3
bba
3
bbab
3
bbaba
3
bbabaa
3
bbabaab
3
b
3
ba
3
bab
3
baba
3
babaa
3
babaab
3
a
3
ab
3
aba
3
abaa
3
abaab
3
b
3
ba
3
baa
3
baab
3
a
3
aa
3
aab
3
a
3
ab
3
b

output:

4 2
3 1
1 23
1 23
1 23
1 23
1 23
1 23
4 2
1 23
1 23
1 23
1 23
1 23
1 23
4 2
2 1
1 23
1 23
1 23
1 23
4 2
3 1
1 23
1 23
1 23
4 2
2 1
1 23
1 23
4 2
1 23
1 23
4 2
3 1
4 2

result:

ok 72 tokens

Test #5:

score: 0
Accepted
time: 1ms
memory: 5948kb

input:

136
4
a
4
ab
4
abb
4
abba
4
abbab
4
abbaba
4
abbabaa
4
abbabaab
4
abbabaabb
4
abbabaabba
4
abbabaabbaa
4
abbabaabbaab
4
abbabaabbaaba
4
abbabaabbaabab
4
abbabaabbaababb
4
abbabaabbaababba
4
b
4
bb
4
bba
4
bbab
4
bbaba
4
bbabaa
4
bbabaab
4
bbabaabb
4
bbabaabba
4
bbabaabbaa
4
bbabaabbaab
4
bbabaabbaab...

output:

8 2
5 2
3 4
3 4
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
8 2
3 4
3 4
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
8 2
5 2
2 6
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
8 2
5 2
2 6
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
1 86
8 2
5 2
2 6
2 6
1 86
1 ...

result:

ok 272 tokens

Test #6:

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

input:

528
5
a
5
ab
5
abb
5
abba
5
abbab
5
abbaba
5
abbabaa
5
abbabaab
5
abbabaabb
5
abbabaabba
5
abbabaabbaa
5
abbabaabbaab
5
abbabaabbaaba
5
abbabaabbaabab
5
abbabaabbaababb
5
abbabaabbaababba
5
abbabaabbaababbab
5
abbabaabbaababbaba
5
abbabaabbaababbabaa
5
abbabaabbaababbabaab
5
abbabaabbaababbabaaba
5
...

output:

16 2
11 1
5 10
5 10
3 9
3 9
3 9
3 9
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
16 2
5 10
5 10
3 9
3 9
3 9
3 9
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344
1 344...

result:

wrong answer 10th words differ - expected: '13', found: '9'