QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#353092 | #1287. Anti-hash Test | Diu | WA | 1ms | 3940kb | C++14 | 2.4kb | 2024-03-13 20:58:51 | 2024-03-13 20:58:51 |
Judging History
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,ans=calc(k+c);
printf("%d %d\n",val,ans);
}else{
int val=1ll*(qpow(2,k)-1)*inv3%mod;
ans=1ll*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: 3940kb
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: 3812kb
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: 0ms
memory: 3868kb
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: -100
Wrong Answer
time: 0ms
memory: 3836kb
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 23 1 23 1 23 1 23 1 23 4 2 3 1 1 23 1 23 1 23 4 2 2 23 1 23 1 23 4 2 1 23 1 23 4 2 3 1 4 2
result:
wrong answer 34th words differ - expected: '1', found: '23'