题解归档 - cf2226G

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2226G
• 本地来源：problems/cf2226G/idea.md
• 题目链接：https://codeforces.com/contest/2226/problem/G
• 原始标题：cf2226G - Stop Spot

思路

cf2226G - Stop Spot

Pattern: Manacher + selected suffix trie + permutation-prefix counting.

Observations:

• The appended part p is a permutation, so no even palindrome can lie fully inside p: the middle two values would have to be equal.
• Palindromes fully inside a are fixed; their count is base.
• Every variable palindrome crosses the boundary and has its center in a or exactly at the boundary.

Boundary centers:

• Let an even center in a reach the right end of a.
• Write L for the prefix length before the palindromic suffix. Then a[L+1..n] must be an even palindrome.
• Such a center contributes lcp(p, reverse(a[1..L])), capped by m.
• L=n is the boundary center with empty suffix.

Trie model:

• For every valid L, insert reverse(a[1..L]) into a trie, capped by:

  • m, because p has length m;
  • the longest all-distinct suffix ending at L, because a permutation prefix cannot contain repeated values.
• Each inserted prefix node stores how many valid L patterns pass through it.
• For a permutation p, the extra palindrome count is the sum of weights on trie nodes visited by its prefix.

Counting permutations:

• DFS the trie.

• At a node of depth d and accumulated score s:

  • choosing a next value not among trie children gives score s for all remaining completions;
  • choosing a child continues with s + weight[child];
  • at depth m, one full permutation is counted.
• This gives cnt[extra] for all possible extra counts.
• Answer is sum cnt[extra]^(base + extra + 1).

Check:

• Brute enumerates all m! permutations for m <= 7.
• Stress compares random repeated arrays.

代码

来源：problems/cf2226G/solution.cpp

/* Author: likely
 * Time: 2026-06-27
**/
#include<bits/stdc++.h>
using namespace std;

const int MOD=998244353;

static int addmod(int a,int b){
    a+=b;
    if(a>=MOD) a-=MOD;
    return a;
}

static int mod_pow(long long a,long long e){
    long long r=1%MOD;
    a%=MOD;
    while(e){
        if(e&1) r=r*a%MOD;
        a=a*a%MOD;
        e>>=1;
    }
    return (int)r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    const int MAXN=1000000;
    vector<int>fact(MAXN+1,1);
    for(int i=1;i<=MAXN;i++) fact[i]=(long long)fact[i-1]*i%MOD;
    while(T--){
        int n,m;
        cin>>n>>m;
        vector<int>a(n+1);
        for(int i=1;i<=n;i++) cin>>a[i];
        vector<int>d2(n,0);
        int l=0,r=-1;
        long long base=0;
        for(int i=0;i<n;i++){
            int k=(i>r)?0:min(d2[l+r-i+1],r-i+1);
            while(i+k<n&&i-k-1>=0&&a[i+k+1]==a[i-k]) k++;
            d2[i]=k;
            base+=k;
            if(i+k-1>r){
                l=i-k;
                r=i+k-1;
            }
        }
        vector<int>unique_len(n+1,0),last(m+1,0);
        int left=1;
        for(int i=1;i<=n;i++){
            left=max(left,last[a[i]]+1);
            unique_len[i]=i-left+1;
            last[a[i]]=i;
        }
        vector<int>head(1,-1),weight(1,0),depth(1,0);
        vector<int>to,nxt;
        unordered_map<long long,int>edge_id;
        edge_id.reserve((size_t)n*2+10);
        auto new_node=[&](int dep)->int{
            int id=(int)head.size();
            head.push_back(-1);
            weight.push_back(0);
            depth.push_back(dep);
            return id;
        };
        auto add_edge=[&](int u,int c,int v){
            to.push_back(v);
            nxt.push_back(head[u]);
            head[u]=(int)to.size()-1;
        };
        for(int L=1;L<=n;L++){
            bool good=false;
            if(L==n){
                good=true;
            }else if(((n-L)&1)==0){
                int len=n-L;
                int cen=(L+n)/2;
                if(cen>=0&&cen<n&&d2[cen]>=len/2) good=true;
            }
            if(!good) continue;
            int cap=min({L,m,unique_len[L]});
            int u=0;
            for(int dep=1;dep<=cap;dep++){
                int c=a[L-dep+1];
                long long key=1LL*u*(m+1)+c;
                auto it=edge_id.find(key);
                int v;
                if(it==edge_id.end()){
                    v=new_node(dep);
                    edge_id.emplace(key,v);
                    add_edge(u,c,v);
                }else{
                    v=it->second;
                }
                u=v;
                weight[u]++;
            }
        }
        unordered_map<long long,int>dist;
        dist.reserve(head.size()*2+10);
        auto add_dist=[&](long long score,long long val){
            if(val%MOD==0) return;
            int &cur=dist[score];
            cur=(cur+val)%MOD;
        };
        vector<pair<int,long long>>st;
        st.push_back({0,0});
        while(!st.empty()){
            auto [u,score]=st.back();
            st.pop_back();
            int child_count=0;
            for(int e=head[u];e!=-1;e=nxt[e]) child_count++;
            int dep=depth[u];
            if(dep==m){
                add_dist(score,1);
            }else{
                int missing=m-dep-child_count;
                if(missing>0) add_dist(score,1LL*missing*fact[m-dep-1]%MOD);
                for(int e=head[u];e!=-1;e=nxt[e]){
                    int v=to[e];
                    st.push_back({v,score+weight[v]});
                }
            }
        }
        int ans=0;
        for(auto [extra,cnt]:dist){
            ans=addmod(ans,mod_pow(cnt,base+extra+1));
        }
        cout<<ans<<"\n";
    }
    return 0;
}