学了五年 KMP

拜谢 oi-wiki。字符串下标从 $0$ 开始，$s_{[l, r]}$ 闭区间子串，定义 $\displaystyle \pi_i = \max_{j \in [0, i]} j[s_{[0, j-1] = s_{[i-j+1, i]}}]$。规定 $\pi_0 = 0$。

朴素求 border 有一个小优化，可以把复杂度从 $O(n^3)$ 降成 $O(n^2)$，这里直接蒯份 oi-wiki 的代码：

// C++ Version
vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++)
    for (int j = pi[i - 1] + 1; j >= 0; j--)  // improved: j=i => j=pi[i-1]+1
      if (s.substr(0, j) == s.substr(i - j + 1, j)) {
        pi[i] = j;
        break;
      }
  return pi;
}

复杂度 $O\left(\left(\sum \pi_i-\pi_{i-1}\right)\times T\right) = O(\pi_{n-1}\times T) = O(n \times T)$，其中 $T$ 是字符串比较的复杂度。

注意到 border 每次至多增长 $1$（我们考虑从 $i-1$ 转移到 $i$），且增长的充要条件是 $s_i = s_{\pi_{i-1}}$。如果不能增长，我们就考虑一种「递归子问题」式的处理方法，即令 $S$ 为「所有出现在 $\pi_{i-1}$ 决策链中的下标集合」，也就是 $\pi$ 定义的那个 $\max$ 里面并且后面的 iversion brackets 为真的 $j$，并且记 $S$ 中的最大值为 $j^{(0)}$，次大值为 $j^{(1)}$，以此类推。又注意到 $s_{0, j-1} = s_{[i-j+1, i]} = s_{\pi_i-j, \pi_i-1}$（$\overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ s_3}^{\pi[i]} ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{\pi[i]} ~ s_{i+1}$），所以得到 $j^{(n)} = \pi_{j^{(n-1)}-1}$。

for (int i=1,j; i<n; ++i) {
    for (j = brd[i-1]; j && s[i] != s[j];) {
        j = brd[j-1];
    }
    brd[i] = j+(s[i] == s[j]);
}

考虑复杂度，即证明我们只会跳 $O(n)$ 次的 border。我记得我两年前证过，好像用到了字符集大小远小于字符串规模的前提。不管了。我他吗不证了。

Trie，爱你

Trie 的空间复杂度实际上是需要均摊证明是 $O(n\times\Sigma)$ 的，其中 $n$ 是所有字符串的总长。

Aho-Corasick DFA

非常喜欢 ouuan 对一些事情的看法与做法，学习应该更贴切于本质而不是功利主义渲染下的作用与价值。

我们需要了解 DFA 是什么。DFA 是一个被描述为 $(\Sigma, Q, start, F, \delta)$ 的五元组：

字符集（$\Sigma$），该自动机只能输入这些字符。

状态集合（$Q$）。如果把一个DFA看成一张有向图，那么 DFA 中的状态就相当于图上的顶点。

起始状态（$start$），$start\in Q$，是一个特殊的状态。起始状态一般用 $s$ 表示，为了避免混淆，本文中使用 $start$。

接受状态集合（$F$），$F\subseteq Q$，是一堆特殊的状态。

转移函数（$\delta$），$\delta$ 是一个接受两个参数返回一个值的函数，其中第一个参数和返回值都是一个状态，第二个参数是字符集中的一个字符。如果把一个DFA看成一张有向图，那么 DFA 中的转移函数就相当于顶点间的边，而每条边上都有一个字符。

—— ouuan

我们先来看 KMP 中的狭义 AC DFA 结构（事实上 KMP 本身即是一个 DFA，不过主体是一条链而已），其失配指针指向当前前缀的最长真后缀构成的字符串在哪个前缀。

所以说 oi-wiki 上将对于失配指针的描述改成长度实际上是不太传统的，但也不影响 oi-wiki 写得非常好。

AC DFA 已经更好理解了，无非是把 border 的定义从链上搬到了 trie 树上。

字符串匹配

我们需要考虑 border 的存在会为字符串匹配产生怎样的影响，传统的朴素做法是以模式串为主元，通过挪动模式串的头指针在文本串中的位置做匹配。当 $[j, m) \neq [i, i+m-j-1]$，也就是说 $[i-j, i)=[0,j)$，然后我舍弃 $[\delta(j-1)+1, j)$ 的匹配长度，再尝试 $j$ 和 $i$。换言之，我想要求到的是以 $i$ 结尾的最长匹配长度。这就是匹配。

总结地说，我们使用失配指针优化匹配的过程，实际上是在找原串中每个前缀的最长后缀，满足这个后缀是模式串的一个前缀，这样看，失配指针的构造就非常自然了。

转而看到 AC DFA 上，当你在 DFA 上的转移不能继续进行时，就会跳到失配指针上，使得你的决策变得更劣（因为不存在不劣的决策，可以理解为一个小贪心吧）。

其他

Q：为什么 AC DFA 上搞事情每个结点可能要继承其失配指针的信息？

A：因为这说明当前结点存在一个极长真后缀是所以插入模式串中的一个。

Part. 1 基本信息

Part. 1-1 SAM 的构成。

SAM 由两个东西构成，一个是一个 DAWG，还有一棵外向树，叫 parent tree。

比如，给你一个字符串 $S=\sf abbabb$，它的 SAM 长成这样：

SAM 的 DAWG 大概可以理解为把字符串的所有后缀插入一个 Trie。当然如果你暴力插，点数为 $\mathcal{O}(n^2)$。

不过显然我们可以把一些重复的结点 rua 在一起，点数差不多就成了 $\mathcal{O}(n)$，还要带个 $2$ 的常数。

然后，$S$ 的子串都可以被 SAM 的 DAWG 上的某条路径表示，很显，对吧。

DAWG 的边就是上图中的黑边，蓝边就是 parent tree 的树边。

Part. 1-2 符号约定

我们称 $S[l,r]$ 为字符串 $S$ 的 $[l,r]$ 的子串，相信大家都懂，下标从 $1$ 开始。

我们称一个集合 $\text{endpos}(S[l,r])$ 为：对于字符串 $S$，$S[l,r]$ 在 $S$ 中出现的区间为 $[l_{1},r_{1}],\cdots,[l_{k},r_{k}]$，$\text{endpos}(S[l,r])=\{r_{1},\cdots,r_{k}\}$。

对于两个子串 $x,y$，如果 $\text{endpos}(x)=\text{endpos}(y)$，则称 $x,y$ 在同一个 $\text{endpos}$ 等价类中。

显然在 DAWG 上，从根节点到一个结点 $u$ 能组成的字符串的长度是不同的（不同的路径组成的字符串长度不一定等），我们称从根节点到一个结点 $u$ 能组成的最长的一个字符串的长度为 $\text{maxlen}(u)$，最短的称为 $\text{minlen}(u)$。

Part. 2 需要知道的

Part. 2-1 $\text{enspos}$ 的性质

引理 1：对于两个 $S$ 的非空子串 $x,y$（不妨设 $|x|<|y|$），若 $\text{endpos}(x)=\text{endpos}(y)$，则 $x$ 为 $y$ 的一个真后缀。

Obviously。

引理 2：对于两个 $S$ 的非空子串 $x,y$（不妨设 $|x|\le|y|$），则

$$ \begin{cases} \text{endpos}(x)\subseteq\text{endpos}(y),x\text{ is a suffix of } y, \\ \displaystyle\\ \text{endpos}(x)\cap\text{endpos}(y),\text{otherwise} \end{cases}

$$ Obviously。 > **引理 3**：在一个 $\text{endpos}$ 等价类中，将类中的所有子串按长度非递增的顺序排序。每个子串都不会比它前一个子串长，与此同时每个子串也是它前一个子串的后缀。换句话说，对于同一等价类的任一两子串，较短者为较长者的后缀，且该等价类中的子串长度恰好覆盖整个区间 $[x,y]$。 由引理 1，可知这些子串不会等长（对于两个串，较短串为较长串的真后缀），后面 obviously。 说得简单一点，把一个等价类里面最长的那个字符串拿出来，其他所有串都是该串的 suffix。 ### Part. 2-2 后缀链接 Link 后缀链接是在原串的 DAWG 上的点连出的边。后缀链接的链接遵循某种规则，且最后构成的是一棵树，我们把后缀链接连出来的树称为 *Parent Tree*，在后文我们将讲解这种规则。 我们先来看看一个串 $S=\sf aababa$ 的 Parent Tree 长成副什么样子：  图是从 command_block 那里拿来的，可以沟通删除。（已经修正了原图的勘误） 为了说明方便，我们以一个任意的等价类来说明，我们称这个等价类中长度最大的串为 $S_{\max}$，同理有 $S_{\min}$。 考虑在 $S_{\max}$ 前面加上一个字符，称为新串为 $S_{\text{new}}$，显然 $S_{\text{new}}$ 一定不和 $S_{\max}$ 在同一等价类里。 我们把上述 *加字符* 的操作看为分裂出儿子。有了这些，我们可以得出一些性质： 1. 设 Parent Tree 上的父亲为 $f$，儿子为 $u$，有 $\text{minlen}(u)=\text{maxlen}(f)+1$，显然。 2. 点数边数皆为 $\mathcal{O}(n)$，不考虑证明，背着。 3. 在 Parent Tree 上，一个结点的父亲一定是该结点的后缀，显然。 最后板子自己理解性背住吧，构造方法不想写了。 ```cpp struct SuffixAutomaton { int ID(char c) { return c-'a'; } struct node { int len,link,ch[26]; }nodes[3000010]; int n,cntot,las,siz[3000010]; char s[1000010]; vector<int> e[3000010]; void init(int len,char c[]) { n=len; for(int i=1;i<=n;++i) s[i]=c[i]; nodes[0].len=las=cntot=0; nodes[0].link=-1; } void extend(char c) { int cur=++cntot,one=las,ano=0; nodes[cur].len=nodes[las].len+1; while(~one&&!nodes[one].ch[ID(c)]) { nodes[one].ch[ID(c)]=cur; one=nodes[one].link; } if(one==-1) nodes[cur].link=0; else { ano=nodes[one].ch[ID(c)]; if(nodes[one].len+1==nodes[ano].len) nodes[cur].link=ano; else { int clone=++cntot; nodes[clone].len=nodes[one].len+1; nodes[clone].link=nodes[ano].link; memcpy(nodes[clone].ch,nodes[ano].ch,sizeof(int)*26); while(~one&&nodes[one].ch[ID(c)]==ano) { nodes[one].ch[ID(c)]=clone; one=nodes[one].link; } nodes[ano].link=nodes[cur].link=clone; } } siz[las=cur]=1; } void pre() { for(int i=1;i<=n;++i) extend(s[i]); for(int i=1;i<=cntot;++i) e[nodes[i].link].push_back(i); } void dfs(int x) { for(int i=0;i<e[x].size();++i) { int y=e[x][i]; dfs(y); siz[x]+=siz[y]; } if(siz[x]^1) ans=max(ans,siz[x]*nodes[x].len); } }SAM; ``` 代码中的 `siz` 是 $\text{endpos}$ 集合大小。

Description

Link.

给定字符串，正整数集合 $A,B$，满足 $\forall u\in A,v\in B,1\le u,v\le n$。

求 $\sum_{i\in A}\sum_{j\in B}\text{LCP}(A,B)$。

Solution

双倍经验是 SvT，只不过 SvT 这屑玩意儿卡常。

先反转串，然后插入 SAM。众所周知

把字符串反转后插入 SAM 后，两个原串的后缀在 parent tree 上的 $\text{LCA}$ 是这两个后缀的 $\text{LCP}$。

然后你就可以搞两个 DP，分别跑 $A$ 子树大小，$B$ 子树大小。

注意根节点需要特殊处理，因为我们是跨子树跑的 DP。不过 SvT 不需要，不知道是不是我的问题（应该就是）。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m,dfn[500010],fa[500010][21],dep[500010],sjc,pos[200010],onepower[500010],anopower[500010],onef[500010],anof[500010];
char s[200010];
LL ans;
struct SuffixAutomaton
{
    #define ID(c) ((c)-'a')
    vector<int> e[500010];
    int n,cntot,las,len[500010],pre[500010],ch[500010][26];
    char s[200010];
    void init(int _n,char c[])
    {
        n=_n;
        for(int i=1;i<=n;++i)    s[i]=c[i];
        cntot=las=1;
    }
    void extend(char c)
    {
        int cur=++cntot,one=las,ano=0;
        len[cur]=len[las]+1,las=cur;
        while(one&&!ch[one][ID(c)])    ch[one][ID(c)]=cur,one=pre[one];
        if(one==0)    pre[cur]=1;
        else
        {
            ano=ch[one][ID(c)];
            if(len[one]+1==len[ano])    pre[cur]=ano;
            else
            {
                int clone=++cntot;
                len[clone]=len[one]+1;
                pre[clone]=pre[ano];
                memcpy(ch[clone],ch[ano],sizeof(ch[ano]));
                while(one&&ch[one][ID(c)]==ano)    ch[one][ID(c)]=clone,one=pre[one];
                pre[ano]=pre[cur]=clone;
            }
        }
    }
    void build()
    {
        for(int i=1;i<=n;++i)    extend(s[i]),pos[i]=las;
        for(int i=2;i<=cntot;++i)    e[pre[i]].emplace_back(i);
    }
}SAM;
void dfs(int x,int las)
{
    dfn[x]=++sjc,fa[x][0]=las,dep[x]=dep[las]+1;
    for(int i=1;i^21;++i)    fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int y : SAM.e[x])    dfs(y,x);
}
int LCA(int one,int ano)
{
    if(dep[one]<dep[ano])    swap(one,ano);
    for(int i=20;~i;--i)    if(dep[fa[one][i]]>=dep[ano])    one=fa[one][i];
    if(one^ano)
    {
        for(int i=20;~i;--i)    if(fa[one][i]^fa[ano][i])    one=fa[one][i],ano=fa[ano][i];
        return fa[one][0];
    }
    else    return one;
}
bool cmp(int one,int ano){return dfn[one]<dfn[ano];}
struct VirtualTree
{
    vector<int> e[500010];
    vector<int> build(vector<int> poi)
    {
        sort(poi.begin(),poi.end(),cmp);
        poi.erase(unique(poi.begin(),poi.end()),poi.end());
        int len=poi.size();
        for(int i=1;i<len;++i)    poi.push_back(LCA(poi[i-1],poi[i]));
        sort(poi.begin(),poi.end(),cmp);
        poi.erase(unique(poi.begin(),poi.end()),poi.end());
        len=poi.size();
        for(int i=1;i<len;++i)    e[LCA(poi[i-1],poi[i])].push_back(poi[i]);
        return poi;
    }
}VRT;
template<class T>
void read(T &hhh)
{
    T x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')    f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')    x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
    if(~f)    hhh=x;
    else    hhh=-x;
}
template<class T>
void write(T x,char las='\n')
{
    static int st[100],top=0;
    if(x<0)    putchar('-'),x=-x;
    do st[++top]=x%10,x/=10; while(x);
    while(top)    putchar(st[top--]^'0');
    putchar(las);
}
void exdfs(int x)
{
    for(int y : VRT.e[x])    exdfs(y),onef[x]+=onef[y],anof[x]+=anof[y];
    for(int y : VRT.e[x])    ans+=(LL)SAM.len[x]*(onef[x]-onef[y])*anof[y];
    ans+=(LL)((onepower[x]&anopower[x])+onepower[x]*anof[x]+anopower[x]*onef[x])*SAM.len[x];
    onef[x]+=onepower[x],anof[x]+=anopower[x];
}
int main()
{
    read(n),read(m);
    scanf("%s",s+1);
    reverse(s+1,s+n+1);
    SAM.init(n,s),SAM.build();
    dfs(1,0);
    while(m--)
    {
        int ones,anos,x;
        read(ones),read(anos);
        vector<int> key,tmp;
        while(ones--)    read(x),key.push_back(pos[n-x+1]),onepower[pos[n-x+1]]=1;
        while(anos--)    read(x),key.push_back(pos[n-x+1]),anopower[pos[n-x+1]]=1;
        tmp=VRT.build(key);
        ans=0,exdfs(tmp[0]);
        write(ans);
        for(int now : tmp)    onef[now]=anof[now]=0,VRT.e[now].clear(),onepower[now]=anopower[now]=0;
    }
    return 0;
}

「ARC 113A」A*B*C

Link.

就是算 $\sum_{i=1}^{k}\sum_{j=1}^{\lfloor\frac{k}{i}\rfloor}\lfloor\frac{k}{j\times j}\rfloor$。

直接调和级数。

#include<cstdio>
long long k;
int main()
{
    scanf("%lld",&k);
    long long ans=0;
    for(long long i=1;i<=k;++i)
    {
        for(long long j=1;j<=k/i;++j)    ans+=(k/i/j);
    }
    printf("%lld\n",ans);
    return 0;
}

「ARC 113B」A^B^C

Link.

扩展欧拉定理裸题，$A^{B^{C}}\bmod10=A^{(B^{C}\bmod\varphi(10))+\varphi(10)}\bmod10$。

#include<cstdio>
long long getphi(long long x)
{
    long long res=x;
    for(long long i=2;i*i<=x;++i)
    {
        if(x%i==0)
        {
            res=res/i*(i-1);
            while(x%i==0)    x/=i;
        }
    }
    if(x>1)    res=res/x*(x-1);
    return res;
}
long long cqpow(long long bas,long long fur,long long mod)
{
    long long res=1;
    while(fur)
    {
        if(fur&1)    res=res*bas%mod;
        bas=bas*bas%mod;
        fur>>=1;
    }
    return res;
}
long long a,b,c;
int main()
{
    scanf("%lld %lld %lld",&a,&b,&c);
    printf("%lld\n",cqpow(a,cqpow(b,c,getphi(10))+getphi(10),10));
    return 0;
}

「ARC 113C」String Invasion

Link.

正序枚举 $i\in[1,n]$，如果满足条件，那么后面的字符串都可以执行操作，则 $ans:=ans+n-i$。

当然，由于后面可能存在一个字符就是 $s_{i}$，所以要记录当前操作的字符，特判 $ans:=ans-1$。

#include<cstdio>
#include<cstring>
int n;
long long ans;
char s[200010];
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    char las=0;
    for(int i=1;i<=n;++i)
    {
        if(i!=n&&s[i]==s[i+1]&&s[i]!=s[i+2]&&s[i]!=las)    ans+=n-i,las=s[i];
        else if(s[i]==las)    --ans;
    }
    printf("%lld\n",ans);
    return 0;
}

「ARC 113D」Sky Reflector

Link.

显然只要 $\forall i\in[1,m],b_{i}\ge a_{\max}$ 即可，那么枚举 $i\in[1,k]=a_{\max}$，有：

$$ ans=\sum_{i=1}^{k}(i^{n}-(i-1)^{n})\times(k-i+1)^{m}\bmod998244353 $$

#include<cstdio>
const int mod=998244353;
long long cqpow(long long bas,int fur)
{
    long long res=1;
    while(fur)
    {
        if(fur&1)    res=res*bas%mod;
        bas=bas*bas%mod;
        fur>>=1;
    }
    return res;
}
int n,m,k;
long long ans;
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    if(n==1)    ans=cqpow(k,m);
    else if(m==1)    ans=cqpow(k,n);
    else
    {
        for(int i=1;i<=k;++i)    ans=(ans+((cqpow(i,n)-cqpow(i-1,n)+mod)%mod)*cqpow(k-i+1,m)%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

「ARC 113E」Rvom and Rsrev

Link.

「ARC 113F」Social Distance

Link.

这种东西怎么写啊。。。

Day 1（好像也没有 Day 2

到了 NK 后发现正好可以进门，于是就什么也没有检查的进去了。

进门前问了一下 LYC 之前问过的一个问题，他说没有头绪，然后就没怎么说话了。

在去考场的途中和大 LJS 瞎扯了一下 CF 的 bitmasks 瘤子题。

小 ljs 在考场外面等的时候问我 KMP 怎么打。（伏笔 x1

我告诉他没有关系，碰见全部哈希（伏笔 x2。

快要进门的时候发现 WXK、TR、高一正在互相进行仪式。

然后就没有什么了。

进了考场之后打开 Dev，把快读之类的东西打了打，果然还是不习惯辣么大个的 Enter。

右边的右边是 WXK，坐下时互相说了句：“好巧啊”，然后互相迷惑地做了一下 orz 动作。

左边的左边是 TLY，直接 yyds。

然后，然后就发题了嘛，打开看见文件夹里一个 string 我就知道事情不对。

此时尧姐的 flag 倒了：“今年考字符串、计数我把这个键盘夹着草稿纸吃了。”

打开 PDF，先用了整整半个小时通读了一下，感觉 T1、T2 简单题，T3、T4 只能骗。

于是乎细读了一下 T1，发现是个 DFS 模拟水题。（当时没有往拓扑想，不过反正都是对的）

然后花了半个小时的样子过完了所有大样例，还很 sb 地认为不会报 int。不过保险起见还是在代码开头和考场的草稿纸（指记事本 text.txt，事实上考场上的草稿纸质量太劣我没用）都写了一句 Beware of your LONG LONG 以提醒自己最后十五分钟再重新考虑会不会爆。

然后看 T2，想了大概五分钟出了一个翻过来枚举就是 $\Theta(n\ln n)$ 大众 84pts 的垃圾做法。

此时想起了 YHN 学长在暑假的时候讲的话：“在考场上有一个暴力就先打一个，可以在正解死亡时应急以及对拍。”

然后就开始打这个 伪·$\Theta(n^{2})$。然后打出了一个 180+ 行的垃圾。

T3 带 SPJ，此时教练的 flag 倒了：“NOIP 不会考带 SPJ 的东西，以后不要考了。”

T3 又是个构造，此时教练的 flag 又倒了：“NOIP 不会考构造，以后不要考了。”

到了后面就根本不想打正解了，只想着调自己的暴力。结果就是调到后面越调越慌，连改思路的想法都没有。

最后就改了个 T1 的 long long，什么也没有干。

于是，NOIP2020 成了至暗时刻。

出来考场后，我问 LYC T2 的复杂度，他说：“$\Theta(Tn\sqrt{n})$”。我当时就以为块 YC 打了个分块。

中午大家一起到某个不知名的地方吃了一个疑似火锅的东西。

桌子上小 ljs 跟我一样 T2 陷在 $\Theta(n^2)$ 潮流中，其他人都打了 84。

然后说着说着 LYC 发现自己 T1 读错了题（后来被证实是出题人语文差，自己也没考虑这些，于是读错题 没 有 关 系），蒙着发现自己也读错了。

然后就觉得，要完，这下没了（本来就没了好吧）。

本来大家都十分快乐的对着自己的答案，然后尧姐冒了一句：“大家不要对了，伤感情。”

于是 LYC 对着这个 T12 没对出错 T34 骗分稳健的人喊了一句：“对了半天没对出错，有优越感了是吧。”

十分奇妙的，本来大家都对吃没有什么兴趣，LYC 和 LJS 这两个饭量小的早就不吃了，结果 TR 点的虾滑来之后一个二个都站了起来。

感觉就这样了吧，NOIP2020 是灰色但打醒的。

Sol.

A 排水系统

找出所有的起点 DFS 即可，可以手动实现一个分数类。

/* Beware of your __INT128 */

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

namespace MySpace {
typedef long long LL;

const __int128 MAXN = 1e5 + 5, MAXS = 10 + 5, MAXE = 1e5 + 5;

__int128 rint () {
    __int128 x = 0, f = 1; char c = getchar ();
    for ( ; c < '0' || c > '9'; c = getchar () )    f = ( c == '-' ? -1 : f );
    for ( ; c >= '0' && c <= '9'; c = getchar () )    x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
    return x * f;
}

template<typename _T>
void wint ( _T x ) {
    if ( x < 0 )    putchar ( '-' ), x = ~ x + 1;
    if ( x > 9 )    wint ( x / 10 );
    putchar ( x % 10 + '0' );
}

__int128 calcGCD ( const __int128 a, const __int128 b ) ;
__int128 calcLCM ( const __int128 a, const __int128 b ) ;

struct GraphSet {
    __int128 to, nx;
    GraphSet ( __int128 T = 0, __int128 N = 0 ) { to = T, nx = N; }
} as[MAXN * 5 * 4];

struct Frac {
    __int128 one, ano;
    Frac ( __int128 O = 0, __int128 A = 0 ) { one = O, ano = A; }
} nds[MAXN];

__int128 n, stn, edn, bgn[MAXN], cnte, ind[MAXN], outd[MAXN], sts[MAXN], eds[MAXN], stnd, ednd, vis[MAXN];

void makeEdge ( const __int128 u, const __int128 v ) { as[++ cnte] = GraphSet ( v, bgn[u] ), bgn[u] = cnte; }
__int128 calcGCD ( const __int128 a, const __int128 b ) { return ! b ? a : calcGCD ( b, a % b ); }
__int128 calcLCM ( const __int128 a, const __int128 b ) { return ( ! a || ! b ) ? 0 : ( __int128 )a / calcGCD ( a, b ) * b; }
void getSimp ( Frac& fr ) { __int128 ret = calcGCD ( fr.one, fr.ano ); if ( ! ret )    fr = Frac (); else fr.one /= ret, fr.ano /= ret; }

void dfs ( const __int128 u ) {
    for ( __int128 i = bgn[u]; i; i = as[i].nx ) {
        __int128 v = as[i].to;
        Frac ad = Frac ( nds[u].one, nds[u].ano * outd[u] );
        getSimp ( ad );
        __int128 ret = calcLCM ( ad.ano, nds[v].ano );
        if ( ! ret )    nds[v] = ad, dfs ( v );
        else {
            __int128 ads = ret / ad.ano, us = ret / nds[v].ano;
            ad.one *= ads, ad.ano *= ads;
            nds[v].one *= us, nds[v].ano *= us;
            nds[v].one += ad.one;
            getSimp ( nds[v] );
            dfs ( v );
        }
    }
    if ( bgn[u] )    nds[u] = Frac ();
}

void Main () {
    n = rint (), stn = rint ();
    for ( __int128 i = 1; i <= n; ++ i ) {
        __int128 eg = rint ();
        for ( __int128 j = 1; j <= eg; ++ j ) {
            __int128 to = rint ();
            makeEdge ( i, to );
            ind[to] ++, outd[i] ++;
        }
    }
    for ( __int128 i = 1; i <= n; ++ i ) {
        if ( ! ind[i] )    sts[++ stnd] = i;
        if ( ! outd[i] )    eds[++ ednd] = i;
    }
    for ( __int128 i = 1; i <= stnd; ++ i )    nds[sts[i]].one = nds[sts[i]].ano = 1;
    sort ( eds + 1, eds + 1 + ednd );
    for ( __int128 i = 1; i <= stnd; ++ i )    dfs ( i );
    for ( __int128 i = 1; i <= ednd; ++ i )    wint ( nds[eds[i]].one ), putchar ( ' ' ), wint ( nds[eds[i]].ano ), putchar ( '\n' );
}
}

int main () {
//    freopen ( "water.in", "r", stdin );
//    freopen ( "water.out", "w", stdout );
    MySpace :: Main ();
    return 0;
}

B 字符串匹配

这里是 $\Theta(Tn\ln n+26Tn)$，我 yy 出来的一个 $\Theta(n\ln n+Tn)$ 的做法由于太过繁杂不想想了。

首先枚举 $AB$ 即循环节，然后挨个往后面跳记个数就好了。

#include <cstdio>
#include <cstring>

namespace mySpace {
typedef long long LL;

const int KEY = 1331;
const int MAXN = ( 1 << 20 ) + 5;

int mul ( const LL a, const LL b, const int p ) { return a * b % p; }
int add ( const int a, const int b, const int p ) { return ( a + b ) < p ? ( a + b ) : ( a + b - p ); }
int sub ( const int a, const int b, const int p ) { return ( a - b ) < 0 ? ( a - b + p ) : ( a - b ); }
struct Value {
    static const int onemod = 19260817, anomod = 998244353;
    int p, q;
    Value () : p ( 0 ), q ( 0 ) {}
    Value ( const int x ) : p ( x ), q ( x ) {}
    Value ( const int a, const int b ) : p ( a ), q ( b ) {}
    Value operator * ( const Value &other ) const { return Value ( mul ( p, other.p, onemod ), mul ( q, other.q, anomod ) ); }
    Value operator + ( const Value &other ) const { return Value ( add ( p, other.p, onemod ), add ( q, other.q, anomod ) ); }
    Value operator - ( const Value &other ) const { return Value ( sub ( p, other.p, onemod ), sub ( q, other.q, anomod ) ); }
    bool operator == ( const Value &other ) const { return p == other.p && q == other.q; }
    bool operator != ( const Value &other ) const { return ! ( Value ( p, q ) == other ); }
} pwr[MAXN], has[MAXN];

int n, mps[MAXN], buc[MAXN][26], suf[MAXN];
char str[MAXN];

void initial () {
    scanf ( "%s", str + 1 ), n = strlen ( str + 1 );
    for ( int i = 1; i <= n; ++ i )    mps[i] = str[i] - 'a';
    bool tmp[26] = {}; int cur = 0;
    for ( int i = 1; i <= n; ++ i ) {
        has[i] = has[i - 1] * KEY + mps[i];
        memcpy ( buc[i], buc[i - 1], sizeof ( int ) * 26 );
        tmp[mps[i]] ^= 1, cur += tmp[mps[i]] ? 1 : -1;
        for ( int j = cur; j < 26; ++ j )    buc[i][j] ++;
    }
    memset ( tmp, 0, sizeof ( tmp ) ), cur = 0;
    for ( int i = n; i; -- i )    tmp[mps[i]] ^= 1, cur += tmp[mps[i]] ? 1 : -1, suf[i] = cur;
}

Value calcHS ( const int l, const int r ) { return has[r] - has[l - 1] * pwr[r - l + 1]; }
void solve () {
    initial (); LL ans = 0;
    for ( int len = 2; len < n; ++ len ) {
        Value tmp = calcHS ( 1, len );
        for ( int nxt = len; nxt < n; nxt += len ) {
            if ( calcHS ( nxt - len + 1, nxt ) != tmp )    break;
            ans += buc[len - 1][suf[nxt + 1]];
        }
    }
    printf ( "%lld\n", ans );
}

void main () {
    pwr[0] = 1;
    for ( int i = 1; i <= MAXN - 5; ++ i )    pwr[i] = pwr[i - 1] * KEY;
    int TC; scanf ( "%d", &TC );
    while ( TC -- > 0 )    solve ();
}
}

int main () {
//    freopen ( "string.in", "r", stdin );
//    freopen ( "string.out", "w", stdout );
    mySpace :: main ();
    return 0;
}

C 移球游戏

首先肯定这是 $n$ 个栈。先看 $n=2$ 的部分分。

这种情况只有黑白两色。

设 $1$ 柱有 $b$ （总共）个黑棋，有 $w$ 个白棋，把 $2$ 柱上 $b$ 个棋子放到 $3$ 柱上，然后重复：

• 把 $1$ 柱顶部所有黑棋放到 $2$ 柱上。
• 然后把 $1$ 柱上所有白棋放到 $3$ 柱。

直到 $1$ 柱为空。

然后把 $3$ 柱上面本属于 $1$ 柱的白棋放回去，又把 $2$ 柱上面的 $b$ 个黑棋放到 $1$ 柱去。

于是乎现在 $1$ 柱的情况大概是这样的：

假设原本是这样的：

$$ \begin{aligned} &\texttt{W W B W W B W W B B B} \\ &\texttt{W B W B B B W B W B W} \end{aligned} $$

那么现在移完后是这样：

$$ \begin{aligned} &\texttt{W W W W W W B B B B B} \\ &\texttt{W B W B B B} \\ &\texttt{W B W B W} \end{aligned} $$

然后我们把此时 $2$ 柱上的棋子全部放到 $3$ 柱上去，然后就划分一下就完了。

后面的事情就简单了，当 $n>2$ 的时候打个分治，一半一半划分染色，然后按着按着整理。

（代码和 CQ 队长 jiangly 对拍过，不过莫名奇妙就变成了基因比照，于是代码就基本变成了 jiangly 的）

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

namespace mySpace {
const int MAXN = 50 + 5, MAXM = 400 + 5, MAXK = 820000 + 5;

int rint () {
    int x = 0, f = 1; char c = getchar ();
    for ( ; c < '0' || c > '9'; c = getchar () )    f = c == '-' ? -1 : f;
    for ( ; c >= '0' && c <= '9'; c = getchar () )    x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
    return x * f;
}

template<typename _T>
void wint ( _T x ) {
    if ( x < 0 )    putchar ( '-' ), x = ~ x + 1;
    if ( x > 9 )    wint ( x / 10 );
    putchar ( x % 10 ^ '0' );
}

struct Stack {
private:
    int stk[MAXM], _top;
public:
    Stack () { memset ( stk, 0, sizeof ( stk ) ), _top = 0; }
    void push ( const int val ) { stk[_top ++] = val; }
    void pop () { if ( _top )    _top --; }
    int at ( const int pos ) { return stk[pos]; }
    int top () { return stk[_top - 1]; }
    int size () { return _top; }
    bool empty () { return _top < 0; }
    void debug ( char c = ' ' ) {
        putchar ( '[' );
        for ( int i = 0; i < _top; ++ i )    printf ( "%d ", stk[i] );
        printf ( "]%c", c ) ;
    }
} clr[MAXN];

struct Answer {
    int one, ano;
    Answer ( int O = 0, int A = 0 ) { one = O, ano = A; }
} ans[MAXK];

int n, m, cnt;

void trans ( const int one, const int ano ) {
    clr[ano].push ( clr[one].top () );
    clr[one].pop ();
    ans[cnt ++] = Answer ( one, ano );
}

void solve ( const int l, const int r, const vector<int>& col ) {
    if ( r - l == 1 )    return;
    int mid = ( l + r ) >> 1;
    int lst = col[0];
    vector<int> onevec, anovec;
    for ( int i = 1; i < r - l; ++ i ) {
        int one = lst, ano = col[i], cnt = 0;
        for ( int j = 0; j < m; ++ j ) {
            if ( clr[one].at ( j ) < mid )    ++ cnt;
        }
        for ( int j = 0; j < cnt; ++ j )    trans ( ano, n );
        for ( int j = m - 1; ~ j; -- j ) {
            if ( clr[one].at ( j ) < mid )    trans ( one, ano );
            else    trans ( one, n );
        }
        for ( int j = 0; j < m - cnt; ++ j )    trans ( n, one );
        for ( int j = 0; j < cnt; ++ j )    trans ( ano, one );
        for ( int j = 0; j < m - cnt; ++ j )    trans ( ano, n );
        for ( int j = 0; j < cnt; ++ j )    trans ( one, ano );
        for ( int j = m - 1; ~ j; -- j ) {
            if ( clr[ano].size () < m && ( clr[n].at ( j ) < mid || clr[one].size () == m ) )    trans ( n, ano );
            else    trans ( n, one );
        }
        bool was = 0;
        for ( int j = 0; j < m; ++ j ) {
            if ( clr[ano].at ( j ) >= mid )    was = 1;
        }
        if ( was )    anovec.push_back ( one ), lst = ano;
        else    onevec.push_back ( ano ), lst = one;
    }
    if ( clr[lst].at ( 0 ) < mid )    onevec.push_back ( lst );
    else    anovec.push_back ( lst );
    solve ( l, mid, onevec ), solve ( mid, r, anovec );
}

void main () {
    n = rint (), m = rint ();
    for ( int i = 0; i < n; ++ i ) {
        for ( int j = 0; j < m; ++ j )    clr[i].push ( rint () - 1 );
    }
    vector<int> col;
    for ( int i = 0; i < n; ++ i )    col.push_back ( i );
    solve ( 0, n, col );
    wint ( cnt ), putchar ( '\n' );
    for ( int i = 0; i < cnt; ++ i ) {
        wint ( ans[i].one + 1 ), putchar ( ' ' );
        wint ( ans[i].ano + 1 ), putchar ( '\n' );
    }
}
}

int main () {
//    freopen ( "ball.in", "r", stdin );
//    freopen ( "ball.out", "w", stdout );
    mySpace :: main ();
    return 0;
}