Logo wfirstzhang 的博客

博客

#808. 三子串拼接回文计数 题目资源

avatar wfirstzhang 2026-10-15 19:40:16

回文拼接：参考算法与正确性

本文为出题人文档，不放入选手附件。下标从 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;
}

}
#endif

plan.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;
}
}
#endif

case_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

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

wfirstzhang Avatar
wfirstzhang
密码是111111
活跃度 近 53 周
查看全年
中文 English

鲁ICP备2025150228号

服务器时间: 2026-10-17 07:32:05 | 开源项目