回文拼接：参考算法与正确性
本文为出题人文档，不放入选手附件。下标从 0 开始，X[i:e] 表示左闭右开的连续子串。
回文起点计数
定义 $p_X(i)$ 为字符串 $X$ 中从 $i$ 开始的非空回文子串数，并令 $p_X(|X|)=0$。
Manacher 求出奇偶回文半径。一个奇中心 $c$、半径 $r$ 对起点区间 $[c-r+1,c]$ 各贡献 1；一个偶中心 $c$、半径 $r$ 对 $[c-r,c-1]$ 各贡献 1。用差分得到整个 $p_X$，时间和空间均为线性。
两串统计
令 $Y$ 为第二个字符串的反串。对第一个字符串 $X$ 的每个起点 $i$，求 $R_{X,Y}(i)$：从 $i$ 开始在 $X$ 中取一个非空子串，并在原第二串中取一个非空子串，使它们拼接为回文的方案数。约定 $R_{X,Y}(|X|)=0$。
设两段长度的较小值为 $\ell$。剥掉相等的外层，必然得到
$$ X[i:i+\ell]=Y[j:j+\ell]. $$
余下的部分恰好属于下列互斥情况之一：为空；是 $X$ 中从 $i+\ell$ 开始的非空回文；是 $Y$ 中从 $j+\ell$ 开始的非空回文。因此
$$ R_{X,Y}(i)=\sum_{\ell\ge1}\sum_{j:\,X[i:i+\ell]=Y[j:j+\ell]} \bigl(1+p_X(i+\ell)+p_Y(j+\ell)\bigr). $$
较短段的长度与外层匹配位置由原方案唯一确定，故没有重计，也不会计入空的原子串。
分块求全部 $R$
把 $X$ 分成长度 $B$ 的块；最后一块可以较短。每对相同子串，按其在 $X$ 中的匹配段是否跨过起点所在块的右边界分类。
匹配段留在块内
每个起点最多枚举 $B$ 个长度。在 $Y$ 上建 SAM，每个状态维护：
occ：结束位置出现次数；weighted：所有结束位置 $e$ 的 $p_Y(e+1)$ 之和。
这两个量均按 suffix link 从长到短传播。沿 SAM 读取 $X[i:e]$，到达状态 $v$ 时，该匹配段的贡献就是
$$ (1+p_X(e))\operatorname{occ}(v)+\operatorname{weighted}(v). $$
时间为 $O(|X|B+|Y|)$。
匹配段跨过块边界
固定起点所在块的右边界 $b$。枚举 $Y$ 中与之对应的分割点 $j$，其中 $1\le j<|Y|$。
令 $l$ 为两边向左匹配的长度，截断至前一块长度；令 $r$ 为向右匹配的长度。用两次 Z 算法求出所有 $j$ 的 $l,r$。右侧模式只需保留至多 $|Y|$ 个字符，左侧模式只需保留至多 $\min(B,|Y|)$ 个字符，所以一个边界只需 $O(|Y|)$ 时间。
对于所有
$$ i\in[b-l,b), $$
左段均能匹配。右段长度可独立选取 $1\dots r$。无论 $i$ 取什么，其贡献都是
$$ w=\sum_{t=1}^{r}\bigl(1+p_X(b+t)+p_Y(j+t)\bigr). $$
用 $p_X,p_Y$ 的前缀和计算 $w$，对 $R[b-l:b]$ 做一次差分区间加。空匹配不贡献。
唯一归属： 一个跨块匹配段只由其起点所在块的右边界处理。它即使跨过更多块，也不会由之后的边界再次处理，因为之后边界的允许起点仅限其紧邻的前一块。
总时间为
$$ O\left(|Y|+|X|B+\frac{|X||Y|}{B}\right). $$
取 $B=\Theta(\sqrt{|Y|})$，若其大于 $|X|$ 就直接把 $X$ 作为一块。实现取约 $\sqrt{6|Y|}$ 以平衡常数。
回到三串
令 $D=\operatorname{rev}(C)$，计算
$$ F_i=R_{A,\operatorname{rev}(B)}(i),\qquad G_j=R_{D,B}(j), $$
以及 $P_B=\sum_i p_B(i)$。
比较原方案中 $|S_A|$ 与 $|S_C|$。剥掉较短者对应的外层匹配后：
- 等长：仅剩 $B$ 中的非空回文，贡献 $P_B$；
- $A$ 较长：剩余是 $A$ 的一段与 $B$ 的一段拼出的回文，贡献 $F$；
- $C$ 较长：反转剩余部分后，贡献 $G$。
定义 $K_A(e)$：$A,D$ 中一对相同非空子串的方案数，要求其中 $A$ 的子串以 $e$ 结束。对称定义 $K_D(f)$。令
$$ K=\sum_e K_A(e)=\sum_f K_D(f). $$
最终答案为
$$ P_BK+\sum_e K_A(e)F_{e+1}+\sum_f K_D(f)G_{f+1}\pmod {998244353}. $$
三种外层长短关系互斥，外层匹配的位置和长度也唯一，故该公式恰好统计每个合法方案一次。
线性计算 $K$
在目标串上建 SAM 并传播 occ。令
$$ H(v)=H(\operatorname{link}(v))+ (\operatorname{len}(v)-\operatorname{len}(\operatorname{link}(v)))\operatorname{occ}(v). $$
扫描另一个串。当当前最长匹配后缀长度为 $q$、对应状态为 $v$ 时，所有匹配后缀的出现次数之和为
$$ H(\operatorname{link}(v))+ (q-\operatorname{len}(\operatorname{link}(v)))\operatorname{occ}(v). $$
这就是该结束位置的 $K$。两个方向各扫描一次即可。
复杂度与整数范围
设 $L=\max(|A|,|B|,|C|)$。总时间 $O(L\sqrt L)$、额外空间 $O(L)$。多次调用的总时间不超过
$$ O\left(\sqrt{\max_i L_i}\sum_i L_i\right). $$
在 $L\le10^5$ 时，$p$ 的前缀和、单个 $R_i$、单个 $K_i$ 与 $K$ 总和均可用有符号 64 位整数保存。但最终公式中的乘积可能远超 64 位，必须先将乘数分别取模，再相乘。模数小于 $10^9$，两模数内整数的乘积可用 64 位整数保存。
所有数据结构都在一次函数调用内重新建立。空的残余串只体现在两串公式中的常数 1，三个被选子串始终要求非空。
gen.cpp
#include "testlib.h"
#include "plan.h"
#include "reference.h"
#include <iostream>
int main(int argc,char**argv) {
registerGen(argc,argv,1);
int id=opt<int>("case",1);
int sample=opt<int>("sample",0);
long long seed=opt<long long>("seed",20261015);
ensuref(sample?1<=sample&&sample<=4:1<=id&&id<=64,"invalid point number");
std::uint64_t base=(std::uint64_t)seed ^ (std::uint64_t)rnd.next(1LL,4611686018427387903LL);
auto cases=pld_plan::make(sample?sample:id,base,sample!=0);
std::cout<<"PLD1\n"<<cases.size()<<'\n';
for(auto&s:cases) {
auto c=pld_cases::make(s);
s.answer=int(pld_reference::count_impl(c.a,c.b,c.c));
std::cout<<s.kind<<' '<<s.na<<' '<<s.nb<<' '<<s.nc<<' '<<s.param<<' '<<s.flags<<' '<<s.seed<<' '<<s.answer<<'\n';
if(s.kind==0)std::cout<<s.a<<'\n'<<s.b<<'\n'<<s.c<<'\n';
}
}reference.h
#ifndef PLD_REFERENCE_H
#define PLD_REFERENCE_H
#include <bits/stdc++.h>
namespace pld_reference {
using namespace std;
using i64 = long long;
const i64 MOD = 998244353;
vector<int> pal_starts(const string& s) {
int n = (int)s.size();
vector<int> odd(n), even(n), diff(n + 1), out(n + 1);
for (int i = 0, l = 0, r = -1; i < n; ++i) {
int k = i > r ? 1 : min(odd[l + r - i], r - i + 1);
while (i - k >= 0 && i + k < n && s[i-k] == s[i+k]) ++k;
odd[i] = k;
++diff[i-k+1]; --diff[i+1];
if (i+k-1 > r) l = i-k+1, r = i+k-1;
}
for (int i = 0, l = 0, r = -1; i < n; ++i) {
int k = i > r ? 0 : min(even[l + r - i + 1], r - i + 1);
while (i-k-1 >= 0 && i+k < n && s[i-k-1] == s[i+k]) ++k;
even[i] = k;
if (k) ++diff[i-k], --diff[i];
if (i+k-1 > r) l = i-k, r = i+k-1;
}
int carry = 0;
for (int i = 0; i < n; ++i) out[i] = (carry += diff[i]);
return out;
}
struct SAM {
struct State {
int next[26], link, len, occ;
i64 weighted, cumulative;
State() : link(-1), len(0), occ(0), weighted(0), cumulative(0) {
fill(next, next+26, -1);
}
};
vector<State> st;
explicit SAM(const string& s, const vector<int>* weights = nullptr) {
st.reserve(s.size()*2 + 1); st.emplace_back();
int last = 0;
for (int i = 0; i < (int)s.size(); ++i) {
int c = s[i]-'a', cur = (int)st.size();
st.emplace_back(); st[cur].len = st[last].len + 1;
st[cur].occ = 1;
if (weights) st[cur].weighted = (*weights)[i+1];
int p = last;
while (p != -1 && st[p].next[c] == -1) {
st[p].next[c] = cur; p = st[p].link;
}
if (p == -1) st[cur].link = 0;
else {
int q = st[p].next[c];
if (st[p].len + 1 == st[q].len) st[cur].link = q;
else {
int clone = (int)st.size();
st.push_back(st[q]); st[clone].len = st[p].len + 1;
st[clone].occ = 0; st[clone].weighted = 0;
while (p != -1 && st[p].next[c] == q) {
st[p].next[c] = clone; p = st[p].link;
}
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
vector<int> cnt(s.size()+1), order(st.size());
for (auto& v : st) ++cnt[v.len];
for (int i = 1; i <= (int)s.size(); ++i) cnt[i] += cnt[i-1];
for (int v = (int)st.size()-1; v >= 0; --v) order[--cnt[st[v].len]] = v;
for (int k = (int)order.size()-1; k > 0; --k) {
int v = order[k], p = st[v].link;
st[p].occ += st[v].occ; st[p].weighted += st[v].weighted;
}
for (int k = 1; k < (int)order.size(); ++k) {
int v = order[k], p = st[v].link;
st[v].cumulative = st[p].cumulative + (i64)(st[v].len-st[p].len)*st[v].occ;
}
}
vector<i64> common_suffix(const string& x) const {
vector<i64> out(x.size());
int v = 0, len = 0;
for (int i = 0; i < (int)x.size(); ++i) {
int c = x[i]-'a';
while (v && st[v].next[c] == -1) {
v = st[v].link; len = st[v].len;
}
if (st[v].next[c] == -1) v = 0, len = 0;
else v = st[v].next[c], ++len;
if (v) {
int p = st[v].link;
out[i] = st[p].cumulative + (i64)(len-st[p].len)*st[v].occ;
}
}
return out;
}
};
vector<int> zfunc(const string& s) {
int n = (int)s.size(); vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; ++i) {
if (i < r) z[i] = min(r-i, z[i-l]);
while (i+z[i] < n && s[z[i]] == s[i+z[i]]) ++z[i];
if (i+z[i] > r) l = i, r = i+z[i];
}
return z;
}
vector<i64> pair_rows(const string& x, const string& y,
const vector<int>& px, const vector<int>& py, int block) {
int n = (int)x.size(), m = (int)y.size();
if (!block) block = max(1, min(n, (int)sqrt(6.0*m)));
vector<i64> out(n+1), diff(n+1), sx(n+2), sy(m+2);
for (int i = 0; i <= n; ++i) sx[i+1] = sx[i] + px[i];
for (int i = 0; i <= m; ++i) sy[i+1] = sy[i] + py[i];
{
SAM sam(y, &py);
for (int i = 0; i < n; ++i) {
int stop = min(n, (i/block+1)*block), v = 0;
for (int e = i; e < stop; ++e) {
v = sam.st[v].next[x[e]-'a'];
if (v == -1) break;
out[i] += (i64)(1+px[e+1])*sam.st[v].occ + sam.st[v].weighted;
}
}
}
if (m > 1) {
string ry(y.rbegin(), y.rend());
for (int b = block; b < n; b += block) {
int plen = min(n-b, m), llen = min({b,block,m});
string text = x.substr(b, plen); text += '#'; text += y;
auto right = zfunc(text);
text = x.substr(b-llen, llen); reverse(text.begin(), text.end());
text += '#'; text += ry;
auto left = zfunc(text);
for (int j = 1; j < m; ++j) {
int a = left[llen+1+m-j], r = right[plen+1+j];
if (!a || !r) continue;
i64 w = r + sx[b+r+1]-sx[b+1] + sy[j+r+1]-sy[j+1];
diff[b-a] += w; diff[b] -= w;
}
}
}
i64 carry = 0;
for (int i = 0; i < n; ++i) out[i] += (carry += diff[i]);
return out;
}
i64 count_impl(const string& a, const string& b, const string& c, int block=0) {
string rb(b.rbegin(),b.rend()), rc(c.rbegin(),c.rend());
auto pa = pal_starts(a), pb = pal_starts(b);
auto prb = pal_starts(rb), prc = pal_starts(rc);
auto ra = pair_rows(a,rb,pa,prb,block);
auto rr = pair_rows(rc,b,prc,pb,block);
auto ka = SAM(rc).common_suffix(a);
auto kr = SAM(a).common_suffix(rc);
i64 palb = accumulate(pb.begin(),pb.end(),0LL);
i64 common = accumulate(ka.begin(),ka.end(),0LL);
i64 ans = (palb%MOD)*(common%MOD)%MOD;
for (int i = 0; i < (int)a.size(); ++i) ans = (ans+(ka[i]%MOD)*(ra[i+1]%MOD))%MOD;
for (int i = 0; i < (int)rc.size(); ++i) ans = (ans+(kr[i]%MOD)*(rr[i+1]%MOD))%MOD;
return ans;
}
}
#endifplan.h
#ifndef PLD_PLAN_H
#define PLD_PLAN_H
#include "require/case_generator.h"
#include <algorithm>
#include <vector>
namespace pld_plan {
using pld_cases::Spec;
using pld_cases::RNG;
inline std::vector<Spec> make(int id, std::uint64_t seed, bool sample=false) {
std::vector<Spec> v;int budget=0;RNG rng(seed);
auto literal=[&](std::string a,std::string b,std::string c) {
Spec s={0,int(a.size()),int(b.size()),int(c.size()),0,0,0,0,a,b,c};
budget+=pld_cases::length(s);v.push_back(s);
};
auto add=[&](int k,int a,int b,int c,int p=3,int f=2,std::uint64_t fixed=0) {
Spec s={k,a,b,c,p,f,fixed?fixed:(rng.next()&UINT64_C(0x7fffffffffffffff)),0,"","",""};
int l=pld_cases::length(s);if(budget+l>100000)return;
budget+=l;v.push_back(s);
};
if(sample) {
if(id==1)literal("a","b","c");
if(id==2)literal("ab","ba","ab");
if(id==3)literal("ab","ab","ab");
if(id==4)literal("aa","aa","aa");
return v;
}
if(id==1) {
std::vector<std::string>words;
for(int n=1;n<=3;++n)for(int mask=0;mask<(1<<n);++mask) {
std::string s(n,'a');for(int i=0;i<n;++i)s[i]+=((mask>>i)&1);words.push_back(s);
}
for(auto&a:words)for(auto&b:words)for(auto&c:words)literal(a,b,c);
} else if(id==2) {
for(int i=0;i<12000;++i)add(3,rng.integer(1,8),rng.integer(1,8),rng.integer(1,8),rng.integer(1,4));
} else if(id==3) {
for(int k=1;k<=20;++k)for(int z=0;z<40;++z)add(k,rng.integer(1,8),rng.integer(1,8),rng.integer(1,8),k==11?3:3+z%5,z%4);
} else if(id==4) {
for(int a=1;a<=8;++a)for(int b=1;b<=8;++b)for(int c=1;c<=8;++c)add(1,a,b,c,0,2);
} else if(id==5) {
const char* triples[][3]={{"a","a","a"},{"a","b","a"},{"ab","ab","ab"},{"ab","ba","ab"},
{"aa","aa","aa"},{"abcba","c","a"},{"a","bc","cba"},{"abc","b","cba"},
{"abba","aa","abba"},{"abaabb","baba","bbabaa"},{"z","a","z"},{"zzzzzzzz","zz","zzzzzzz"}};
for(auto&t:triples)literal(t[0],t[1],t[2]);
for(int i=0;i<6000;++i)add(3,rng.integer(1,8),rng.integer(1,8),rng.integer(1,8),2+i%3,i%4);
} else if(id==6) {
for(int i=0;i<100000;++i)add(3,1,1,1,i%3==0?1:i%3==1?2:26,i%4);
} else if(id==7) {
for(int i=0;i<2000;++i) {
std::uint64_t s=rng.next()&UINT64_C(0x7fffffffffffffff);
int n=1+i%8;add(3,n,n,n,2,0,s);add(3,1,1,1,26,2);
add(3,n,n,n,2,0,s);add(3,n,n,n,2,1,s);add(3,n,n,n,2,2,s);
}
} else if(id==8) {
for(char a='a';a<='z';++a)for(char b='a';b<='z';++b) {
literal(std::string(1,a),std::string(1,b),std::string(1,a));
literal(std::string(2,a),std::string(3,b),std::string(2,b));
}
} else if(id==9) {
for(int i=0;i<100;++i)add(3,1000,1000,1000,i%3==0?2:i%3==1?3:26);
} else if(id==10) {
for(int i=0;i<100;++i)add(i%2?5:6,1000,999-i%5,1000,1+i%37,i%4);
} else if(id==11) {
for(int i=0;i<100;++i)add(12+i%3,1000,1000-i%5,997+i%4,i%2,i%4);
} else if(id==12) {
const int ns[]={1,2,3,15,16,17,31,32,33,63,64,65,127,128,129,255,256,257,316,317,318,447,448,449,511,512,513,773,774,775,776,999,1000};
for(int round=0;round<7;++round)for(int n:ns)add(round%2?6:16,n,std::max(1,n-1),n,round%2?7:31,round%4);
} else if(id==13) {
const int thin[]={1,2,3,7,31,127};
for(int i=0;i<100;++i) {
int q=thin[i%6],axis=i%3;
add(4+i%3,axis==0?q:1000,axis==1?q:1000,axis==2?q:1000,2+i%7,i%4);
}
} else if(id==14) {
for(int i=0;i<1600;++i)add(3,1+i%60,1+(i*37)%60,1+(i*19)%60,1+i%6,i%4);
} else if(id==15) {
for(int i=0;i<100;++i)add(9+i%12,1000,1000,1000,i%12==2?8:31,i%4);
} else if(id==16) {
while(budget<100000){int n=std::min(100000-budget,rng.integer(1,1000));add(1+rng.integer(0,19),n,rng.integer(1,n),rng.integer(1,n),7,rng.integer(0,3));}
} else if(id==17) {
add(1,100000,100000,100000,0,2);
} else if(id==18) {
for(int n:{70000,20000,9000,998,1,1})add(1,n,std::max(1,n/2),std::max(1,n-7),0,2);
} else if(id==19) {
add(1,99991,99989,99990,0,2);add(1,1,9,2,0,2);
} else if(id==20) {
for(int i=0;i<100000;++i)add(1,1,1,1,0,2);
} else if(id>=21 && id<=40) {
int k=id-20,p=3;
if(k==5 || k==6)p=317;
if(k==7)p=769;
if(k==8)p=774;
if(k==11)p=15;
if(k==14)p=1;
if(k==16)p=1023;
if(k==17)p=26;
add(k,100000,100000,100000,p,2);
} else if(id>=41 && id<=52) {
const int ps[]={2,7,31,127,313,317,509,769,774,775,997,1024};
int j=id-41;add(j%2?6:5,100000,99999-j,99997-j,ps[j],j%4);
} else if(id==53) {
add(17,100000,1,99999,2,2);
} else if(id==54) {
add(4,1,100000,99991,3,2);
} else if(id==55) {
add(6,99991,100000,1,31,2);
} else if(id==56) {
add(19,2,100000,3,2,2);
} else if(id==57) {
const int ns[]={40000,1,30000,7,20000,9992};
for(int i=0;i<6;++i)add(i%2?3:16,ns[i],ns[i],std::max(1,ns[i]-1),i%2?26:313,i%4);
} else if(id==58) {
for(int i=0;i<4;++i)add(8+i*3,25000,24999-i,25000,i==1?14:127,i%4);
} else if(id==59) {
while(budget<100000){int n=std::min(100000-budget,rng.integer(1,3000));add(5+rng.integer(0,15),n,std::max(1,n-3),std::max(1,n-7),31,rng.integer(0,3));}
} else if(id==60) {
add(12,50000,49999,49997,3,2);add(13,50000,49997,49999,3,2);
} else if(id==61) {
add(16,50000,50000,50000,4093,2);add(6,50000,50000,50000,4093,2);
} else if(id==62) {
std::uint64_t s=rng.next()&UINT64_C(0x7fffffffffffffff);
add(16,50000,49991,49993,509,0,s);add(16,50000,49991,49993,509,1,s);
} else if(id==63) {
std::uint64_t s=rng.next()&UINT64_C(0x7fffffffffffffff);
for(int f=0;f<4;++f)add(6,25000,24989,24997,317,f,s);
} else if(id==64) {
for(int k:{4,8,16,18})add(k,25000,24999,24997,k==16?1023:3,2);
}
if(v.empty() || budget>100000)throw std::runtime_error("invalid plan");
return v;
}
}
#endifcase_generator.h
#ifndef PLD_CASE_GENERATOR_H
#define PLD_CASE_GENERATOR_H
#include <algorithm>
#include <cstdint>
#include <stdexcept>
#include <string>
#include <vector>
namespace pld_cases {
struct Spec {
int kind, na, nb, nc, param, flags;
std::uint64_t seed;
int answer;
std::string a, b, c;
};
struct Case { std::string a, b, c; };
// The exact unsigned operations below specify a portable, reproducible PRNG.
class RNG {
std::uint64_t state;
public:
explicit RNG(std::uint64_t seed) : state(seed) {}
std::uint64_t next() {
std::uint64_t z = (state += UINT64_C(0x9e3779b97f4a7c15));
z = (z ^ (z >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
z = (z ^ (z >> 27)) * UINT64_C(0x94d049bb133111eb);
return z ^ (z >> 31);
}
int integer(int l, int r) { return l + int(next() % (std::uint64_t(r-l)+1)); }
};
inline std::string reversed(std::string x) {
std::reverse(x.begin(),x.end()); return x;
}
inline std::string random_word(int n, int alphabet, RNG &rng, int shift=0) {
std::string s(n,'a');
for (char &c:s) c=char('a'+shift+rng.integer(0,alphabet-1));
return s;
}
inline std::string cycle(const std::string &s, int n, int shift=0) {
std::string t(n,'a');
for(int i=0;i<n;++i)t[i]=s[(i+shift)%s.size()];
return t;
}
inline std::string mirror_word(int n, int alphabet, RNG &rng, int shift=0) {
std::string s=random_word(n,alphabet,rng,shift);
for(int i=0;i<n/2;++i)s[n-1-i]=s[i];
return s;
}
inline std::string runs(int n,int length,RNG &rng) {
std::string s; s.reserve(n); int letter=rng.integer(0,2);
while(int(s.size())<n) {
int take=std::min(n-int(s.size()),rng.integer(std::max(1,length/2),std::max(1,length*3/2)));
s.append(take,char('a'+letter));letter=(letter+rng.integer(1,2))%3;
}
return s;
}
inline std::string debruijn(int order) {
std::vector<int>a(2*order+2);std::string s;
struct Rec {
static void go(int t,int p,int k,std::vector<int>&a,std::string&s) {
if(t>k){if(k%p==0)for(int i=1;i<=p;++i)s+=char('a'+a[i]);return;}
a[t]=a[t-p];go(t+1,p,k,a,s);
for(int j=a[t-p]+1;j<2;++j){a[t]=j;go(t+1,t,k,a,s);}
}
};
Rec::go(1,1,order,a,s);return s;
}
inline Case make(const Spec &s) {
if(s.kind==0)return {s.a,s.b,s.c};
RNG rng(s.seed);Case t;
int n=std::max({s.na,s.nb,s.nc}),p=std::max(1,s.param);
if(s.kind==1) {
char c=char('a'+rng.integer(0,25));
t={std::string(s.na,c),std::string(s.nb,c),std::string(s.nc,c)};
} else if(s.kind==2) {
t={std::string(s.na,'a'),std::string(s.nb,'b'),std::string(s.nc,'c')};
} else if(s.kind==3) {
p=std::min(26,p);
t={random_word(s.na,p,rng),random_word(s.nb,p,rng),random_word(s.nc,p,rng)};
} else if(s.kind==4) {
std::string base=random_word(n+97,std::min(26,p),rng);
t={cycle(base,s.na,0),reversed(cycle(base,s.nb,13)),reversed(cycle(base,s.nc,31))};
} else if(s.kind==5 || s.kind==6) {
std::string period=random_word(std::min(p,n),3,rng);
t={cycle(period,s.na,0),reversed(cycle(period,s.nb,rng.integer(0,int(period.size())-1))),
reversed(cycle(period,s.nc,rng.integer(0,int(period.size())-1)))};
if(s.kind==6)for(std::string *v:{&t.a,&t.b,&t.c}) {
int count=1+rng.integer(0,3);
for(int z=0;z<count;++z) {
int i=z==0?int(v->size()/2):z==1?0:z==2?int(v->size()-1):rng.integer(0,int(v->size())-1);
(*v)[i]=char('a'+((*v)[i]-'a'+rng.integer(1,2))%3);
}
}
} else if(s.kind==7) {
t={runs(s.na,p,rng),runs(s.nb,p,rng),runs(s.nc,p,rng)};
} else if(s.kind==8) {
t={std::string(s.na,'a'),std::string(s.nb,'a'),std::string(s.nc,'a')};
for(std::string *v:{&t.a,&t.b,&t.c}) {
int choice=rng.integer(0,3),len=int(v->size());
int i=choice==0?0:choice==1?len-1:choice==2?len/2:s.param%len;
(*v)[i]='b';
}
} else if(s.kind==9) {
std::string base(n+97,'a');
for(int i=0;i<int(base.size());++i) {
unsigned x=unsigned(i);int parity=0;
while(x){parity^=1;x&=x-1;}base[i]=char('a'+parity);
}
t={cycle(base,s.na),reversed(cycle(base,s.nb,13)),reversed(cycle(base,s.nc,31))};
} else if(s.kind==10) {
std::string a="a",b="ab";
while(int(b.size())<n+97){std::string c=b+a;a=b;b=c;}
t={cycle(b,s.na),reversed(cycle(b,s.nb,13)),reversed(cycle(b,s.nc,31))};
} else if(s.kind==11) {
int order=1;while(order<16 && (1<<order)<n)++order;
std::string base=debruijn(std::min(order,p));
t={cycle(base,s.na),reversed(cycle(base,s.nb,13)),reversed(cycle(base,s.nc,31))};
} else if(s.kind==12 || s.kind==13) {
t={random_word(s.na,3,rng),random_word(s.nb,3,rng,3),random_word(s.nc,3,rng)};
if(s.kind==12 && s.na>=3) {
int u=std::min(s.nc,s.na/3),v=std::min(s.nb,s.na/3);
int ci=(s.nc-u)/2,bi=(s.nb-v)/2;
t.a=reversed(t.c.substr(ci,u))+reversed(t.b.substr(bi,v))+mirror_word(s.na-u-v,3,rng,6);
}
if(s.kind==13 && s.nc>=3) {
int u=std::min(s.na,s.nc/3),v=std::min(s.nb,s.nc/3);
int ai=(s.na-u)/2,bi=(s.nb-v)/2;
t.c=mirror_word(s.nc-u-v,3,rng,6)+reversed(t.b.substr(bi,v))+reversed(t.a.substr(ai,u));
}
} else if(s.kind==14) {
t={std::string(s.na,'a'),s.param==0?std::string(s.nb,'b'):random_word(s.nb,2,rng,1),std::string(s.nc,'a')};
} else if(s.kind==15) {
t={random_word(s.na,3,rng),random_word(s.nb,26,rng),random_word(s.nc,3,rng,23)};
} else if(s.kind==16) {
p=std::min(p,n);
std::vector<std::string>pool;
for(int i=0;i<7;++i)pool.push_back(random_word(p,3,rng));
auto stream=[&](int len,char separator) {
std::string v;v.reserve(len+p+1);
while(int(v.size())<len){v+=pool[rng.integer(0,6)];v+=separator;}
v.resize(len);return v;
};
t={stream(s.na,'x'),reversed(stream(s.nb,'y')),reversed(stream(s.nc,'z'))};
} else if(s.kind==17) {
std::string base=random_word(n,std::min(26,p),rng);
t={cycle(base,s.na),mirror_word(s.nb,std::min(26,p),rng),reversed(cycle(base,s.nc))};
int i=rng.integer(0,s.nc-1);t.c[i]=char('a'+(t.c[i]-'a'+1)%26);
} else if(s.kind==18) {
std::string base="a";int level=1;
while(int(base.size())<n+97){base=base+char('a'+level%26)+base;++level;}
t={cycle(base,s.na),reversed(cycle(base,s.nb,13)),reversed(cycle(base,s.nc,31))};
} else if(s.kind==19) {
t={mirror_word(s.na,std::min(26,p),rng),mirror_word(s.nb,std::min(26,p),rng),mirror_word(s.nc,std::min(26,p),rng)};
} else if(s.kind==20) {
std::string base;
for(int k=1;int(base.size())<n+97;k=k>=4096?1:k*2) {
base+=std::string(k,'a');base+='b';base+=std::string(k,'a');base+='c';
}
t={cycle(base,s.na),reversed(cycle(base,s.nb,13)),reversed(cycle(base,s.nc,31))};
} else throw std::runtime_error("unknown generator kind");
if(s.flags&1)t={reversed(t.c),reversed(t.b),reversed(t.a)};
if(s.flags&2) {
std::string letters="abcdefghijklmnopqrstuvwxyz";
for(int i=25;i>0;--i)std::swap(letters[i],letters[rng.integer(0,i)]);
for(std::string *v:{&t.a,&t.b,&t.c})for(char &c:*v)c=letters[c-'a'];
}
return t;
}
inline int length(const Spec&s){return std::max({s.na,s.nb,s.nc});}
}
#endif