QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#455490 | #1287. Anti-hash Test | cqbzly | WA | 0ms | 3568kb | C++14 | 5.5kb | 2024-06-26 15:18:08 | 2024-06-26 15:18:09 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define rz resize
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int mod=1e9+7;
int T,tp,sz;
ll n;
string str,str0;
struct SAM{
struct node{
int link,len,occ,to[2];
};
vector<node>t;
vector<vector<int>>G;
vector<int>cnt;
int tot,last;
void extend(int c){
int cur=++tot,p=last;
t[cur].len=t[p].len+1;
while(p!=-1&&!t[p].to[c]){
t[p].to[c]=cur;
p=t[p].link;
}
if(p!=-1){
int q=t[p].to[c];
if(t[q].len==t[p].len+1){
t[cur].link=q;
}
else{
int clone=++tot;
for(int i=0;i<2;i++)t[clone].to[i]=t[q].to[i];
t[clone].link=t[q].link,t[clone].len=t[p].len+1;
t[q].link=t[cur].link=clone;
while(p!=-1&&t[p].to[c]==q){
t[p].to[c]=clone;
p=t[p].link;
}
}
}
t[cur].occ++;
last=cur;
}
void dfs(int u){
for(auto v:G[u]){
dfs(v);
t[u].occ+=t[v].occ;
}
}
void build(int n){
t.rz((1<<n+1)+5);
G.rz((1<<n+1)+5);
cnt.rz((1<<n+1)+5);
t[0].link=-1;
for(int i=0;i<1<<n;i++)extend(__builtin_popcount(i)&1);
for(int i=1;i<=tot;i++){
G[t[i].link].pb(i);
}
dfs(0);
for(int i=1;i<=tot;i++){
cnt[t[i].occ]=(cnt[t[i].occ]+t[i].len-t[t[i].link].len)%mod;
}
}
pair<int,int>qry(string &str){
int it=0,o=1;
for(int i=0;i<str.size();i++){
int c=str[i]-'a';
if(!t[it].to[c]){
o=0;
break;
}
it=t[it].to[c];
}
if(!o){
return {0,-1};
}
return {t[it].occ,cnt[t[it].occ]};
}
}sam[21];
ll fpow(ll x,ll y=mod-2){
ll z(1);
for(;y;y>>=1){
if(y&1)z=z*x%mod;
x=x*x%mod;
}return z;
}
ll calc(ll n,int f=0){
if(n<0)return 0;
ll res;
if(n%2==0)res=((fpow(2,n+1)-2)*fpow(3)+f*(n%2==0))%mod;
else res=((fpow(2,n+1)-1)*fpow(3)+f*(n%2==0))%mod;
return (res+mod)%mod;
}
ll calc0(ll n,int f){
if(!f){
if(n==1)return 1;
if(n==2)return 4;
return 13*fpow(4,n-3)%mod;
}
if(n==1)return 1;
if(n==2)return 6;
return 21*fpow(4,n-3)%mod;
}
pair<ll,ll>sol(){
sz=str.size();
ll c=0;
while(1){
int o=-1;
for(int i=0;i<sz-1;i++){
if(str[i]==str[i+1]){
o=i;
break;
}
}
if(o==-1)break;
str0.clear();
for(int i=o%2;i<=o;i+=2){
if(str[i]=='b')str0+='a';
else str0+='b';
}
for(int i=o+1;i<sz;i+=2){
if(i+1<sz&&str[i]==str[i+1])return {0,-1};
if(str[i]=='a')str0+='a';
else str0+='b';
}
str=str0,sz=str.size(),c++;
//cout<<str<<" "<<n<<"\n";
}
//cout<<str<<" "<<n<<"\n";
if(sz>=5)return {0,-1};
bool x=str[0]-'a';
if(sz==4)c+=3,x^=1;
if(sz==3)c+=2,x=1;
if(sz==2)c+=1;
//答案只和c,x有关
//算的是n-c阶串里面ab,ba总出现次数+(x^1)*(n-c mod 2 == 0)
if(c>n||c==n&&x)return {0,-1};
//缩出来是a/b,原串也只能是a/b
if(sz==1){
return {fpow(2,n-1),2};
}
//出现次数为1(??)
//此时缩出来可能是(n,0),也可能是(n-1,0/1)
if(c+1>=n){
return {1,(calc0(n,0)+calc0(n-1,0)+calc0(n-1,1))%mod};
}
//calc0(c,0/1):缩出来为(c,0/1)的等价类个数
if(n-c&1){
return {calc(n-c,x^1),(calc0(c,0)+calc0(c,1))%mod};
}
return {calc(n-c,x^1),calc0(c,x)};
}
// string get(string str){
// sz=str.size();
// while(1){
// int o=-1;
// for(int i=0;i<sz-1;i++){
// if(str[i]==str[i+1]){
// o=i;
// break;
// }
// }
// if(o==-1)break;
// str0.clear();
// for(int i=o%2;i<=o;i+=2){
// if(str[i]=='b')str0+='a';
// else str0+='b';
// }
// for(int i=o+1;i<sz;i+=2){
// if(i+1<sz&&str[i]==str[i+1])return "fail";
// if(str[i]=='a')str0+='a';
// else str0+='b';
// }
// str=str0,sz=str.size(),n--;
// //cout<<str<<" "<<n<<"\n";
// }
// return str;
// }
int main(){
// freopen("thuemorse.in","r",stdin);
// freopen("thuemorse.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
for(int i=1;i<=5;i++)sam[i].build(i);
// for(int i=1;i<=6;i++){
// cout<<"len:"<<i<<"\n";
// for(int j=0;j<1<<i;j++){
// string tmp;
// for(int k=0;k<i;k++){
// if(j>>k&1)tmp+='b';
// else tmp+='a';
// }
// cout<<tmp<<" "<<get(tmp)<<"\n";
// }
// }
cin>>T;tp=1;
while(T--){
cin>>n>>str;
pair<ll,ll>tmp;
if(n<=5){
tmp=sam[n].qry(str);
}
else{
tmp=sol();
}
if(!tp)cout<<tmp.fi<<"\n";
else cout<<tmp.fi<<" "<<tmp.se<<"\n";
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3568kb
input:
4 10 a 10 abba 5 abbabaabbaababbabaababbaabbabaab 20 ababab
output:
512 2 171 4 1 344 0 -1
result:
wrong answer 7th words differ - expected: '-1', found: '0'