A

考虑对串的反串建后缀树，答案就是叶子节点个数。

注意到这时的叶子节点一定是一段前缀，如果一个前缀 $s[1\ldots i]$ 是叶子节点当且仅当它不属于任何一个点的 border 集合，所以问题变成了求每个前缀的 border 集合的并的大小，用 kmp 解决即可。

这里发现一个结论：每个前缀的 border 集合的并的大小等于 $\max{fail_i}$。

证明要考虑这个命题等价于叶子节点在值域上是连续的一段后缀，然后考虑反证：假设前缀 $x$ 不属于但是 $y$ 属于，一定能从 $y$ 属于的那个前缀找出一部分变成 $x$ 属于的。（然而我考试直接找规律）

所以有个结论：后缀树的叶子节点个数，每个前缀的 border 集合的并的大小，本质不同的 $fail_i$ 的个数，$\text{max} fail_i$ 的值是相等的。

不管怎么说，即使在 NOIP 赛场上遇到字符串题也要想想能否用后缀树的思想方便优化。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;

char str[MAXN];
int n;
int nxt[MAXN];

int main(){
    scanf("%s",str+1);n = strlen(str+1);
    int j = 0;nxt[0] = -1;nxt[1] = 0;int ans = 0;
    FOR(i,2,n){
        while(j && str[i] != str[j+1]) j = nxt[j];
        if(str[i] == str[j+1]) ++j;
        else j = 0;
        nxt[i] = j;
        ans = std::max(ans,nxt[i]);
    }
    printf("%d\n",n-ans);
    return 0;
}

B

首先一个很松的上界的是 $ans \leq n$，我们设所有三元组三个数的和的和为 $S$，三元组个数为 $k$，可以发现 $kn = S \geq 3(1+2+\ldots+k)$，可以得到 $k \leq \lfloor \frac{2n}{3}\rfloor -1$。

写个剪枝搜索应该是能跑出来 $n \leq 17$ 的，于是打表可以发现规律。

我们将 $n$ 按照 $n \bmod 3$ 分类，我们发现 $n \bmod 3=0$ 比较特殊，找找这种方案的规律：

首先我们只需要考虑二元组 $(a_i,b_i)$ 满足和互不相同，$a_i$ 互不相同，$b_i$ 互不相同即可。

我们 $a_i,b_i$ 的值域都是 $[1,ans]$，我们考虑 $a_i$ 前面全放奇数后面全放偶数，然后把 $b_i$ 最小的若干个倒着和 $a_i$ 的奇数部分匹配，剩下的倒着和 $a_i$ 的偶数部分匹配。举个 $n=12$ 的例子：

1 4
3 3
5 2
7 1
2 7
4 6
6 5

首先 $a_i,b_i$ 一定互不相同。然后发现这样排列上一个和下一个的和一定会相差 $1$，所以都满足条件。

$n \bmod 3 = 1$ 的答案是不变的，改一下 $c_i$ 就行了。

$n \bmod 3 = 2$ 的答案变了，我们让 $a_i$ 整体加一，$c_i$ 整体加一，发现 $a,c$ 都可以放 $1$ 了，然后 $b$ 放 $n-2$ 即可。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e5 + 5;
int a[MAXN],b[MAXN],c[MAXN],n,ans;
bool vis[3][MAXN];

inline void check(){
    assert(ans == (2*n-3)/3);
    // DEBUG(ans);
    FOR(i,1,ans){
        // DEBUG(i);
        assert(a[i]+b[i]+c[i] == n);
        assert(!vis[0][a[i]]);
        assert(!vis[1][b[i]]);
        assert(!vis[2][c[i]]);
        vis[0][a[i]] = vis[1][b[i]] = vis[2][c[i]] = 1;
    }
}

int main(){
    scanf("%d",&n);
    if(n == 1){
        puts("0");
        return 0;
    }
    if(n == 2){
        puts("0");
        return 0;
    }
    if(n%3 == 0){
        ans = 2*(n/3)-1;
        printf("%d\n",ans);
        int t = 0;
        for(int i = 1;i <= ans;i += 2) a[++t] = i;
        int t1 = t;
        for(int i = 2;i <= ans;i += 2) a[++t] = i;
        t = 0;
        ROF(i,t1,1) b[i] = ++t;
        ROF(i,ans,t1+1) b[i] = ++t;
        FOR(i,1,ans) c[i] = n-a[i]-b[i];
        FOR(i,1,ans) printf("%d %d %d\n",a[i],b[i],c[i]);
        check();
        return 0;
    }
    if(n%3 == 1){
        --n;
        ans = 2*(n/3)-1;
        printf("%d\n",ans);
        int t = 0;
        for(int i = 1;i <= ans;i += 2) a[++t] = i;
        int t1 = t;
        for(int i = 2;i <= ans;i += 2) a[++t] = i;
        t = 0;
        ROF(i,t1,1) b[i] = ++t;
        ROF(i,ans,t1+1) b[i] = ++t;
        FOR(i,1,ans) c[i] = n-a[i]-b[i]+1;
        FOR(i,1,ans) printf("%d %d %d\n",a[i],b[i],c[i]);
        ++n;
        check();
        return 0;
    }
    if(n%3 == 2){
        n -= 2;
        ans = 2*(n/3)-1;
        int t = 0;
        for(int i = 1;i <= ans;i += 2) a[++t] = i;
        int t1 = t;
        for(int i = 2;i <= ans;i += 2) a[++t] = i;
        t = 0;
        ROF(i,t1,1) b[i] = ++t;
        ROF(i,ans,t1+1) b[i] = ++t;
        FOR(i,1,ans) c[i] = n-a[i]-b[i]+1;
        FOR(i,1,ans) a[i]++;
        // 第一列有1 第三列有1 
        ++ans;
        n += 2;
        a[ans] = 1;c[ans] = 1;b[ans] = n-2;
        printf("%d\n",ans);
        FOR(i,1,ans) printf("%d %d %d\n",a[i],b[i],c[i]);
        check();
        return 0;
    }
    return 0;
}

C

首先注意数字互不相同，所以能分成若干条链，限制形如某条链上相邻的两个点原序列不能相邻（注意我这里思考的链的元素是相邻关系，也就是若干个 pair ，所以选了链上一个点对应了固定了原序列两个点，选了相邻两个对应固定三个，不相连两个对应固定四个）

考虑容斥，枚举有几个相邻的位置 $i$，有一对相邻的位置就可以将两个点并起来，所以排列的方案数就是 $(n-i)!$。

现在只需要求出来有 $i$ 个相邻的位置的方案数就好了。

链与链之间的关系是独立的，我们考虑如果只有一条链怎么做（就是样例 $1$ 的情况）。

我们钦定链上一些连通块选了，那么每个连通块可以正着也可以反着，对答案有 $2$ 的贡献。于是搞个 dp：$f_{i,j,0/1}$ 考虑前 $i$ 个 pair ，选了 $j$ 个 pair ，上一个是否选。转移如果上一个是 $0$ 并且这一个是 $1$ 方案数就要 $\times 2$。

不同链之间是独立的；直接背包合并是爆炸的，不如把所有链拼在一起，在分隔点打标记，每次强制断开即可。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5000+5;
const int ha = 998244353;
int n,k,a[MAXN];

namespace Subtask1{
    inline bool check(){
        return n <= 10;
    }
    
    int p[MAXN];
    
    inline void Solve(){
        FOR(i,1,n) p[i] = i;
        int ans = 0;
        do{
            bool flag = 1;
            FOR(i,2,n) if(std::abs(a[p[i-1]]-a[p[i]]) == k) {flag = 0;break;}
            ans += flag;
        }while(std::next_permutation(p+1,p+n+1));
        printf("%d\n",ans);exit(0);
    }
}

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

namespace Subtask2{
    int f[MAXN][MAXN][2],fac[MAXN];
    inline bool check(){
        return n <= 5000;
    }
    
    bool qd[MAXN];
    int g[MAXN];
    std::map<int,int> S;
    int to[MAXN],len[MAXN],tot;
    bool vis[MAXN];
    
    inline void Solve(){
        FOR(i,1,n) S[a[i]] = i;
        FOR(i,1,n){
            S[a[i]] = 0;
            to[i] = S[a[i]+k];
        }
        int sz = 0;
        FOR(i,1,n){
            if(!vis[i]){
                int v = i;++tot;
                 while(v){
                     ++len[tot];vis[v] = 1;
                     v = to[v];
                 }
                 len[tot]--;
                 if(!len[tot]) --tot;
                 else sz += len[tot];
            }
        }
        int sm = 0;
        FOR(i,1,tot){
            sm += len[i];
            qd[sm+1] = 1;
        }
        f[0][0][0] = 1;
        fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
        FOR(i,1,sz){
            FOR(j,0,i){
                f[i][j][0] = (f[i-1][j][0]+f[i-1][j][1])%ha;
                if(qd[i]){
                    if(j) f[i][j][1] = 2ll*(f[i-1][j-1][0]+f[i-1][j-1][1])%ha;
                }
                else{
                    if(j) add(f[i][j][1],f[i-1][j-1][1]);
                    if(j) add(f[i][j][1],2ll*f[i-1][j-1][0]%ha);
                }
            }
        }
        FOR(i,0,sz) g[i] = (f[sz][i][0]+f[sz][i][1])%ha;
        int ans = 0;
        FOR(i,0,sz){// 选了几个球
            int gx = 1ll*fac[n-i]*g[i]%ha;
            if(i&1) gx = ha-gx;
            add(ans,gx);
        }
        printf("%d\n",ans);
    }
}

int main(){
    scanf("%d%d",&n,&k);
    FOR(i,1,n) scanf("%d",a+i);
    if(Subtask1::check()) Subtask1::Solve();
    if(Subtask2::check()) Subtask2::Solve();
    return 0;
}
/*
注意 这个题没有相同的数
所以限制只有 O(n) 对

n个球 染黑m个 连续段
*/