c++ 最傻的方法

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 998244353;

// 快速幂
long long qpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

// 模逆元（费马小定理）
long long inv(long long x) {
    return qpow(x, MOD - 2);
}

// 计算前缀函数（next数组），0-based
vector<int> get_next(const vector<int>& s) {
    int n = s.size();
    vector<int> nxt(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = nxt[i-1];
        while (j > 0 && s[i] != s[j])
            j = nxt[j-1];
        if (s[i] == s[j])
            j++;
        nxt[i] = j;
    }
    return nxt;
}

// KMP匹配，返回text跑完后匹配pat的最长前缀长度
int kmp_match(const vector<int>& pat, const vector<int>& nxt, const vector<int>& text) {
    int j = 0;
    int m = text.size();
    for (int i = 0; i < m; ++i) {
        while (j > 0 && text[i] != pat[j])
            j = nxt[j-1];
        if (text[i] == pat[j])
            j++;
    }
    return j;
}

// 计算val(X,Y)：X前缀与Y后缀匹配的所有k^i之和
long long calc_val(const vector<int>& X, const vector<int>& nxt_X, 
                   const vector<int>& Y, const vector<long long>& powk) {
    int l = kmp_match(X, nxt_X, Y);
    long long res = 0;
    while (l > 0) {
        res = (res + powk[l]) % MOD;
        l = nxt_X[l-1];
    }
    return res;
}

// 计算Steve的获胜概率
long long calc_P(const vector<int>& S, const vector<int>& T, 
                 int n, const vector<long long>& powk) {
    vector<int> nxt_S = get_next(S);
    vector<int> nxt_T = get_next(T);
    
    long long valSS = calc_val(S, nxt_S, S, powk);
    long long valTT = calc_val(T, nxt_T, T, powk);
    long long valST = calc_val(S, nxt_S, T, powk);
    long long valTS = calc_val(T, nxt_T, S, powk);
    
    long long numerator = (valTT - valST + MOD) % MOD;
    long long denominator = (valSS + valTT - valST - valTS) % MOD;
    denominator = (denominator + MOD) % MOD;
    
    return numerator * inv(denominator) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tid, t;
    cin >> tid >> t;
    const long long inv2 = 499122177; // 1/2 mod 998244353
    
    while (t--) {
        int n, k;
        cin >> n >> k;
        
        if (tid <= 8) { // 子问题一：计算概率
            vector<int> S(n), T(n);
            for (int i = 0; i < n; ++i) cin >> S[i];
            for (int i = 0; i < n; ++i) cin >> T[i];
            
            vector<long long> powk(n + 1);
            powk[0] = 1;
            for (int i = 1; i <= n; ++i)
                powk[i] = powk[i-1] * k % MOD;
            
            cout << calc_P(S, T, n, powk) << '\n';
        } else { // 子问题二：构造序列
            vector<int> T(n);
            for (int i = 0; i < n; ++i) cin >> T[i];
            
            vector<long long> powk(n + 1);
            powk[0] = 1;
            for (int i = 1; i <= n; ++i)
                powk[i] = powk[i-1] * k % MOD;
            
            // 候选1：首位等于T[0]
            vector<int> S1(n);
            S1[0] = T[0];
            for (int i = 1; i < n; ++i)
                S1[i] = T[i-1];
            
            long long P1 = calc_P(S1, T, n, powk);
            if (P1 > inv2) {
                for (int i = 0; i < n; ++i)
                    cout << S1[i] << " ";
                cout << '\n';
                continue;
            }
            
            // 候选2：首位不等于T[0]
            vector<int> S2(n);
            int c = (T[0] == 1) ? 2 : 1;
            S2[0] = c;
            for (int i = 1; i < n; ++i)
                S2[i] = T[i-1];
            
            for (int i = 0; i < n; ++i)
                cout << S2[i] << " ";
            cout << '\n';
        }
    }
    return 0;
}