QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#353085 | #1287. Anti-hash Test | Diu | WA | 1ms | 5980kb | C++14 | 2.4kb | 2024-03-13 20:49:57 | 2024-03-13 20:49:59 |
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){
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;
printf("%d %d\n",val,calc(c+1)%mod);
}else{
int val=1ll*(qpow(2,k)-1)*inv3%mod;
printf("%d %d\n",val,calc(c+1)%mod);
}
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: 0
Wrong Answer
time: 1ms
memory: 5980kb
input:
4 10 a 10 abba 5 abbabaabbaababbabaababbaabbabaab 20 ababab
output:
512 2 171 6 1 344 -1
result:
wrong answer 4th words differ - expected: '4', found: '6'