Znzryb's Blog

2026 杭电春季联赛-1003-回文串（ABA‘ 是这个回文串的形式）

Posted on 2026-03-21 Edited on 2026-04-06

题目大意

题目描述
给定两个长度均为 $n$ 的小写字母字符串 $S$ 和 $T$ 。
你需要在 $S$ 中选取一个子串 $S'$ ，在 $T$ 中选取一个子串 $T'$ （空串不算作子串），并将 $T'$ 拼接在 $S'$ 的后面组成一个新的字符串。
求共有多少种选取方式，使得拼接后的新字符串是一个回文串。
注：选取方式由子串在原串中的起始和终止位置决定；回文串指正读和反读都相同的字符串。

输入格式
第一行输入一个整数表示测试组数 $T$ （ $T \le 10$ ）。
接下来每组数据输入两行，分别表示字符串 $S$ 和 $T$ 。
数据保证两个字符串长度相等且 $n \le 2000$ 。

输出格式
对于每组数据，输出一行整数，表示能组成回文串的子串选取方案数。

样例

样例输入

2
ab
ac
aba
bba

样例输出

1
2

2
15

样例解释
对于第一组样例， $S = \text{"ab"}$ ， $T = \text{"ac"}$ 。合法的选取方式共 $2$ 种：

选取 $S[1 \dots 1] = \text{"a"}$ 和 $T[1 \dots 1] = \text{"a"}$ ，拼接得到 $\text{"aa"}$ ，是回文串。
选取 $S[1 \dots 2] = \text{"ab"}$ 和 $T[1 \dots 1] = \text{"a"}$ ，拼接得到 $\text{"aba"}$ ，是回文串。

对于第二组样例， $S = \text{"aba"}$ ， $T = \text{"bba"}$ 。合法的选取方式共 $15$ 种，列举其中几种情况：

选取 $S[1 \dots 1] = \text{"a"}$ 和 $T[3 \dots 3] = \text{"a"}$ ，拼接得到 $\text{"aa"}$ 。
选取 $S[2 \dots 2] = \text{"b"}$ 和 $T[1 \dots 1] = \text{"b"}$ ，拼接得到 $\text{"bb"}$ 。
选取 $S[2 \dots 2] = \text{"b"}$ 和 $T[2 \dots 2] = \text{"b"}$ ，拼接得到 $\text{"bb"}$ 。
选取 $S[1 \dots 2] = \text{"ab"}$ 和 $T[2 \dots 3] = \text{"ba"}$ ，拼接得到 $\text{"abba"}$ 。
选取 $S[1 \dots 3] = \text{"aba"}$ 和 $T[2 \dots 3] = \text{"ba"}$ ，拼接得到 $\text{"ababa"}$ 。
以此类推，满足条件的下标区间组合总共有 $15$ 种。

思路讲解

完全理解 manacher

void Solve() {
    string s;
    string t;
    cin >> s >> t;
    string rev_t = t;
    reverse(all(rev_t));
    ll szs = SZ(s), szt = SZ(t);
    vector<ll> ps = manacher(s);
    vector<ll> pt = manacher(rev_t);
    // 以 i 为起点的这个回文串数量
    vector<ll> cntS(szs + 3), cntT(szt + 3);
    for (int i = 0; i < SZ(ps); ++i) {
        ll r = ps[i] / 2;
        if (r == 0) {
            continue;
        }
        ll pos = i / 2;
        cntS[pos - r + 1]++;
        cntS[pos + 1]--;
    }
    for (int i = 0; i < SZ(pt); ++i) {
        ll r = pt[i] / 2;
        if (r == 0) {
            continue;
        }
        ll pos = i / 2;
        cntT[pos - r + 1]++;
        cntT[pos + 1]--;
    }
    // 上面是在
    partial_sum(all(cntS), cntS.begin());
    partial_sum(all(cntT), cntT.begin());
#ifdef LOCAL
    debug1d(cntS);
    debug1d(cntT);
#endif
		// 最长公共子后缀
    vector<vector<ll> > lcsuf(szs, vector<ll>(szt));
    ll ans = 0;
    for (int i = 0; i < szs; ++i) {
        for (int j = 0; j < szt; ++j) {
            ll lans = 0;
            if (i - 1 >= 0 && j - 1 >= 0) {
                lans = lcsuf[i - 1][j - 1];
            }
            lcsuf[i][j] = lans;
            if (s[i] == rev_t[j]) {
                lcsuf[i][j]++;
            } else {
                lcsuf[i][j] = 0;
            }
            // 加一是因为还有空的情况，即 s 和 rev_t 都不提供 B
            ll add = lcsuf[i][j] * (cntS[i + 1] + cntT[j + 1] + 1);
            ans += add;
        }
    }
    cout << ans << "\n";
}

AC代码

TLE，这个代码是这个 $O(n^2)$ 的，但是还是这个哈希表还是有点慢，被卡了。

源代码

/**
 * Problem: 回文串
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1197&pid=1003
 * Created: 2026-03-21 01:42:31
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT, testcase;

/*
 *
 */
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<ll, null_type, less<>, rb_tree_tag,
    tree_order_statistics_node_update>;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();

struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};

struct U {
    using u128 = __uint128_t;
    static constexpr ll MOD = (1ULL << 61) - 1;

    ll v; // always in [0, MOD)

    // --- constructors ---
    U() : v(0) {
    }

    U(ll x) {
        ll t = x % MOD;
        if (t < 0) t += MOD;
        v = (ll) t;
    }

    // explicit U(ull x) {
    //     ll s = (x & MOD) + (x >> 61);
    //     if (s >= MOD) s -= MOD;
    //     v = s;
    // }

    // --- core ops ---
    static inline ll add(ll a, ll b) {
        ll s = a + b;
        if (s >= MOD) s -= MOD;
        return s;
    }

    static inline ll sub(ll a, ll b) {
        return (a >= b) ? (a - b) : (a + MOD - b);
    }

    static inline ll mul(ll a, ll b) {
        u128 t = (u128) a * b; // < 2^122
        ll s = ll(t & MOD) + ll(t >> 61); // 1-step fold
        if (s >= MOD) s -= MOD; // at most one subtract needed
        return s;
    }

    // --- operator overloads ---
    U &operator+=(const U &o) {
        v = add(v, o.v);
        return *this;
    }

    U &operator-=(const U &o) {
        v = sub(v, o.v);
        return *this;
    }

    U &operator*=(const U &o) {
        v = mul(v, o.v);
        return *this;
    }

    friend U operator+(U a, const U &b) {
        a += b;
        return a;
    }

    friend U operator-(U a, const U &b) {
        a -= b;
        return a;
    }

    friend U operator*(U a, const U &b) {
        a *= b;
        return a;
    }

    friend bool operator==(const U &a, const U &b) { return a.v == b.v; }
    friend bool operator!=(const U &a, const U &b) { return a.v != b.v; }
    friend bool operator<(const U &a, const U &b) { return a.v < b.v; }
    friend bool operator>(const U &a, const U &b) { return a.v > b.v; }
    friend bool operator<=(const U &a, const U &b) { return a.v <= b.v; }
    friend bool operator>=(const U &a, const U &b) { return a.v >= b.v; }
};

const U base = 131;

// AC https://vjudge.net/solution/65151535 string matching 测试了find函数功能
// 2025/11/4
// AC https://www.luogu.com.cn/record/245201000 测试了这个push，pop，以及增强get鲁棒性。
struct HS {
    // 字符串哈希模版
    vector<U> hs, powBase;
    U hashval;
    ll n;
    string s;
    // 需要注意的是，字符串哈希和数字一样，都是越前面是越高位。
    // 内部采用 0-based 下标，hs[i] 表示 s[0..i] 的哈希值。
    HS(const string &ls) {
        // 使用const 引用才能绑定到常值对象上
        n = SZ(ls);
        s = ls;
        hs.assign(n, 0);
        powBase.assign(n + 1, 0);
        powBase[0] = 1;
        for (ll i = 1; i <= n; ++i) {
            powBase[i] = powBase[i - 1] * base;
        }
        if (n > 0) {
            hs[0] = U(s[0]);
            for (ll i = 1; i < n; ++i) {
                hs[i] = hs[i - 1] * base + U(s[i]);
            }
            hashval = hs[n - 1];
        } else {
            hashval = 0;
        }
    }

    // get(l, r): 返回 s[l..r] 的哈希（0-based, inclusive）
    // 函数有一定鲁棒性，即使遇到超界问题也能自动纠正
    U get(ll l, ll r) {
        if (n == 0) return 0;
        l = max(0ll, l);
        r = min(n - 1, r);
        if (l > r) return 0;
        if (l == 0) return hs[r];
        return hs[r] - hs[l - 1] * powBase[r - l + 1];
    }

    // get(l): 返回 s[l..n-1] 的哈希（0-based）
    U get(ll l) {
        return get(l, n - 1);
    }

    // 返回ls在s中的出现次数
    ll find(const string &ls) {
        U hxfind = 0;
        ll m = SZ(ls);
        if (m == 0) return n + 1;
        if (m > n) return 0;
        for (ll i = 0; i < m; ++i) {
            hxfind = hxfind * base + ls[i];
        }
        ll res = 0;
        for (ll r = m - 1; r < n; ++r) {
            U hx = get(r - m + 1, r);
            if (hx == hxfind) {
                res++;
            }
        }
        return res;
    }

    void pop() {
        if (n == 0) return;
        n--;
        s.pop_back();
        if (n == 0) {
            hs.clear();
            hashval = 0;
            return;
        }
        hs.pop_back();
        hashval = hs.back();
    }

    void push(char c) {
        s.push_back(c);
        if (n == 0) {
            hs.push_back(U(c));
        } else {
            hs.push_back(hs.back() * base + U(c));
        }
        n++;
        hashval = hs.back();
        if (SZ(powBase) <= n) {
            powBase.push_back(powBase.back() * base);
        }
    }
};

// refer cp algorithm
// https://cp-algorithms.com/string/manacher.html
// AC https://acm.hdu.edu.cn/contest/view-code?cid=1180&rid=12078
// 2026-03-21 把不用的宏给删掉了
vector<ll> manacher_odd(string s) {
    int n = SZ(s);
    s = '$' + s + '^';
    vector<ll> p(n + 2);
    ll l = 0, r = 1; // (l,r) 是开区间，其内部是这个回文子串
    for (int i = 1; i <= n; ++i) {
        // 保底半径
        p[i] = min(r - i, p[l + r - i]);
        // 暴力外扩
        while (s[i - p[i]] == s[i + p[i]]) {
            // 因为有哨兵，永不越界
            p[i]++;
        }
        if (i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<ll>(p.begin() + 1, p.end() - 1);
}

vector<ll> manacher(const string &s) {
    string t;
    for (auto c: s) {
        t += '#'; // 千万不要    t+='#'+'c'
        t += c;
    }
    t += '#';
    auto res = manacher_odd(t);
    return vector<ll>(res.begin() + 1, res.end() - 1);
}

// 返回的radius要除以二，i&1的位置是空格，偶数长度回文串，0-based

void Solve() {
    string s;
    string t;
    cin >> s >> t;
    string rev_t = t;
    reverse(all(rev_t));
    ll szs = SZ(s), szt = SZ(t);
    vector<ll> ps = manacher(s);
    vector<ll> pt = manacher(rev_t);
    vector<ll> cntS(szs + 3), cntT(szt + 3);
    for (int i = 0; i < SZ(ps); ++i) {
        ll r = ps[i] / 2;
        if (r == 0) {
            continue;
        }
        // if (i & 1) {
        //     ll pos = i / 2;
        //     cntS[pos - r + 1]++;
        //     cntS[((pos + 1) + r - 1) + 1]--;
        // } else {
        ll pos = i / 2;
        cntS[pos - r + 1]++;
        cntS[pos + 1]--;
        // }
    }
    for (int i = 0; i < SZ(pt); ++i) {
        ll r = pt[i] / 2;
        if (r == 0) {
            continue;
        }
        // if (i & 1) {
        //     ll pos = i / 2;
        //     cntT[pos - r + 1]++;
        //     cntT[]--;
        // } else {
        ll pos = i / 2;
        cntT[pos - r + 1]++;
        cntT[pos + 1]--;
        // }
    }
    partial_sum(all(cntS), cntS.begin());
    partial_sum(all(cntT), cntT.begin());
#ifdef LOCAL
    debug1d(cntS);
    debug1d(cntT);
#endif

    HS hash1(s), hash2(rev_t);
    gp_hash_table<ll, ll, chash> hs_cntOcc, hs_cntPal;
    for (int i = 0; i < szt; ++i) {
        for (int j = i; j < szt; ++j) {
            auto hx = hash2.get(i, j).v;
            hs_cntOcc[hx]++;
            hs_cntPal[hx] += cntT[j + 1];
        }
    }
    ll ans = 0;
    for (int i = 0; i < szs; ++i) {
        for (int j = i; j < szs; ++j) {
            auto hx = hash1.get(i, j).v;
            ll res = 1;
            res += cntS[j + 1];
            auto itOcc = hs_cntOcc.find(hx);
            auto itPal = hs_cntPal.find(hx);
            if (itOcc != hs_cntOcc.end()) {
                ans += res * itOcc->second;
            }
            if (itPal != hs_cntPal.end()) {
                ans += itPal->second;
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve();
    return 0;
}

/*


// 最长公共子后缀
    vector<vector<ll> > lcsuf(szs, vector<ll>(szt));
    for (int i = 0; i < szs; ++i) {
        for (int j = 0; j < szt; ++j) {
            ll lans = 0;
            if (i - 1 >= 0 && j - 1 >= 0) {
                lans = lcsuf[i - 1][j - 1];
            }
            lcsuf[i][j] = lans;
            if (s[i] == rev_t[j]) {
                lcsuf[i][j]++;
            }
        }
    }
*/

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1197&rid=19239

源代码

/**
 * Problem: 回文串
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1197&pid=1003
 * Created: 2026-03-21 01:42:31
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT, testcase;

/*
 *
 */

// refer cp algorithm
// https://cp-algorithms.com/string/manacher.html
// AC https://acm.hdu.edu.cn/contest/view-code?cid=1180&rid=12078
// 2026-03-21 把不用的宏给删掉了
vector<ll> manacher_odd(string s) {
    int n = SZ(s);
    s = '$' + s + '^';
    vector<ll> p(n + 2);
    ll l = 0, r = 1; // (l,r) 是开区间，其内部是这个回文子串
    for (int i = 1; i <= n; ++i) {
        // 保底半径
        p[i] = min(r - i, p[l + r - i]);
        // 暴力外扩
        while (s[i - p[i]] == s[i + p[i]]) {
            // 因为有哨兵，永不越界
            p[i]++;
        }
        if (i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<ll>(p.begin() + 1, p.end() - 1);
}

vector<ll> manacher(const string &s) {
    string t;
    for (auto c: s) {
        t += '#'; // 千万不要    t+='#'+'c'
        t += c;
    }
    t += '#';
    auto res = manacher_odd(t);
    return vector<ll>(res.begin() + 1, res.end() - 1);
}

// 返回的radius要除以二，i&1的位置是空格，偶数长度回文串，0-based

void Solve() {
    string s;
    string t;
    cin >> s >> t;
    string rev_t = t;
    reverse(all(rev_t));
    ll szs = SZ(s), szt = SZ(t);
    vector<ll> ps = manacher(s);
    vector<ll> pt = manacher(rev_t);
    vector<ll> cntS(szs + 3), cntT(szt + 3);
    for (int i = 0; i < SZ(ps); ++i) {
        ll r = ps[i] / 2;
        if (r == 0) {
            continue;
        }
        // if (i & 1) {
        //     ll pos = i / 2;
        //     cntS[pos - r + 1]++;
        //     cntS[((pos + 1) + r - 1) + 1]--;
        // } else {
        ll pos = i / 2;
        cntS[pos - r + 1]++;
        cntS[pos + 1]--;
        // }
    }
    for (int i = 0; i < SZ(pt); ++i) {
        ll r = pt[i] / 2;
        if (r == 0) {
            continue;
        }
        // if (i & 1) {
        //     ll pos = i / 2;
        //     cntT[pos - r + 1]++;
        //     cntT[]--;
        // } else {
        ll pos = i / 2;
        cntT[pos - r + 1]++;
        cntT[pos + 1]--;
        // }
    }
    partial_sum(all(cntS), cntS.begin());
    partial_sum(all(cntT), cntT.begin());
#ifdef LOCAL
    debug1d(cntS);
    debug1d(cntT);
#endif
    vector<vector<ll> > lcsuf(szs, vector<ll>(szt));
    ll ans = 0;
    for (int i = 0; i < szs; ++i) {
        for (int j = 0; j < szt; ++j) {
            ll lans = 0;
            if (i - 1 >= 0 && j - 1 >= 0) {
                lans = lcsuf[i - 1][j - 1];
            }
            lcsuf[i][j] = lans;
            if (s[i] == rev_t[j]) {
                lcsuf[i][j]++;
            } else {
                lcsuf[i][j] = 0;
            }
            ll add = lcsuf[i][j] * (cntS[i + 1] + cntT[j + 1] + 1);
            ans += add;
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve();
    return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1197&rid=19239

// 最长公共子后缀
    vector<vector<ll> > lcsuf(szs, vector<ll>(szt));
    for (int i = 0; i < szs; ++i) {
        for (int j = 0; j < szt; ++j) {
            ll lans = 0;
            if (i - 1 >= 0 && j - 1 >= 0) {
                lans = lcsuf[i - 1][j - 1];
            }
            lcsuf[i][j] = lans;
            if (s[i] == rev_t[j]) {
                lcsuf[i][j]++;
            }
        }
    }
*/

心路历程（WA，TLE，MLE……）

完全理解 manacher

Posted on 2026-03-20 Edited on 2026-03-21

manacher

马拉车算法其实和这个 kmp，z 函数还是有异曲同工之妙的。

我们维护一个最远的回文串边界，记为 r。


// refer cp algorithm
// https://cp-algorithms.com/string/manacher.html
// AC https://acm.hdu.edu.cn/contest/view-code?cid=1180&rid=12078
// 2026-03-21 把不用的宏给删掉了
vector<ll> manacher_odd(string s){
    int n=SZ(s);
    s='$'+s+'^';
    vector<ll> p(n+2);
    ll l=0,r=1;     // (l,r) 是开区间，其内部是这个回文子串
    for(int i=1;i<=n;++i){
        // 保底半径
        p[i]=min(r-i,p[l+r-i]);
        // 暴力外扩
        while (s[i-p[i]]==s[i+p[i]]) { // 因为有哨兵，永不越界
            p[i]++;
        }
        if(i+p[i]>r){
            l=i-p[i],r=i+p[i];
        }
    }
    return vector<ll>(p.begin()+1,p.end()-1);
}
vector<ll> manacher(const string &s){
    string t;
    for(auto c:s){
        t+='#';     // 千万不要    t+='#'+'c'
        t+=c;
    }
    t+='#';
    auto res=manacher_odd(t);
    return vector<ll>(res.begin()+1,res.end()-1);
}
// 返回的radius要除以二，i&1的位置是空格，偶数长度回文串，0-based

可以这样子使用这个差分，得到以该点起点的的这个回文串的数量。

vector<ll> ps = manacher(s);
vector<ll> cntS(szs + 3);
for (int i = 0; i < SZ(ps); ++i) {
    ll r = ps[i] / 2;
    if (r == 0) {
        continue;
    }
    ll pos = i / 2;
    cntS[pos - r + 1]++;
    cntS[pos + 1]--;
}
partial_sum(all(cntS), cntS.begin());

完全理解隔板法（stars and bars）（插板法应用的特征）

Posted on 2026-03-20 Edited on 2026-04-06

隔板法的思想就是，把 a 插入 d 个空格当中，换为给 a 加上 d-1 个隔板。

为什么是这个公式呢？不难发现，我们可以把 a 个球和 d-1 个隔板放在一起进行乱排，模拟可以为 0 的情况。

$C_{N+K-1}^{K-1}=C_{N+K-1}^{N}$ 我认为前面一个更容易理解。

要求这个题目要求 $x_{i}\geq a_{i}$ ，也可以使用这个插板法。

The 21st Hunan Provincial Collegiate Programming Contest——2025-湖南省赛-I. Tearing Paper

这道题目，隔板法是有效的，是因为隔板法其实是要求插入元素的这个顺序是不重要的，那么这道题目，细想之下，确实如此。

经过抽象以后，这道题目需要求解的内容如上。

不难发现，我们其实只关注这个 U R 之间的相对关系，说白了就是两个 U 之间隔了几个 R？只要这个不变，路径是不会改变的。

The 21st Hunan Provincial Collegiate Programming Contest——2025-湖南省赛-H. Prime Segments

Posted on 2026-03-20 Edited on 2026-04-06

题目大意

题目描述
给定一个长度为 $n$ 的正整数序列 $a$ 。
求该序列中有多少个连续子段的和为素数。换言之，计算满足 $1 \le l \le r \le n$ 且 $\sum_{i=l}^r a_i$ 为素数的数对 $(l, r)$ 的数量。

输入格式
第一行包含一个整数 $T$ （ $1 \le T \le 10^4$ ），表示测试用例的数量。
每个测试用例包含两行：
第一行为一个整数 $n$ （ $1 \le n \le 10^6$ ），表示序列的长度。
第二行为 $n$ 个整数 $a_1, a_2, \dots, a_n$ （ $1 \le a_i \le 10^6$ ，且单组测试数据内 $\sum a_i \le 10^6$ ），表示序列的元素。
保证同一个文件内所有测试用例的 $n$ 的总和不超过 $10^6$ ，所有测试用例的 $\sum a_i$ 的总和不超过 $10^6$ 。

输出格式
对于每个测试用例，输出一行一个整数，表示和为素数的子段数量。

样例

输入：

2
4
1 2 3 4
12
1 1 4 5 1 4 1 9 1 9 8 10

输出：

1
2

5
16

样例解释
在第一个样例中，满足条件的 $(l,r)$ 数对如下：
$l=1, r=2$ ：该子段的和为 $3$ 。
$l=2, r=2$ ：该子段的和为 $2$ 。
$l=2, r=3$ ：该子段的和为 $5$ 。
$l=3, r=3$ ：该子段的和为 $3$ 。
$l=3, r=4$ ：该子段的和为 $7$ 。

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）

The 21st Hunan Provincial Collegiate Programming Contest——2025-湖南省赛-I. Tearing Paper

Posted on 2026-03-19 Edited on 2026-04-06

题目大意

题目描述

在一个 $n \times m$ 的网格平面上，有一个关键区域。该区域是一个闭矩形，其四个顶点的坐标分别为 $(a,b)$ 、 $(a,d)$ 、 $(c,d)$ 、 $(c,b)$ ，其中 $0 \le a < c \le n$ 且 $0 \le b < d \le m$ 。

现在会随机选择一条从 $(0,0)$ 到 $(n,m)$ 的合法路径。合法路径是指每一步只能向右（ $x$ 坐标加 $1$ ）或向上（ $y$ 坐标加 $1$ ）的格点路径。

这条路径必定会将整个平面分成“左上”和“右下”两部分（允许其中一部分为空）。我们关注的是该关键区域是否会被这条路径切断。如果整个闭矩形区域完全位于路径的同一侧（完全在“左上”部分或完全在“右下”部分），则称该关键区域保持“完整”；否则视为被路径切断。

求在所有等概率选择的合法路径中，关键区域保持“完整”的概率。答案需要对 $998244353$ 取模。

输入格式

第一行包含一个整数 $T$ （ $1 \le T \le 10^4$ ），表示测试用例的数量。

接下来每行代表一个测试用例，包含六个整数 $n, m, a, b, c, d$ （ $1 \le n \le 10^3$ ， $1 \le m \le 10^6$ ， $0 \le a < c \le n$ ， $0 \le b < d \le m$ ），其含义如题目描述所示。

输出格式

对于每个测试用例，单独输出一行一个整数，表示关键区域保持“完整”的概率对 $998244353$ 取模后的结果。

样例输入

3
3 3 1 1 2 2
3 3 0 0 3 3
3 3 0 1 3 2

样例输出

1
2
3

1
299473306
199648871

样例解释

在第一个测试用例中，关键区域的大小为 $1 \times 1$ 。它永远不会被任何路径切断，因此保持完整的概率为 $1$ 。

在第二个测试用例中，关键区域的大小为 $3 \times 3$ ，即覆盖了整个纸张。由于除非其中一部分为空，否则撕裂路径总是将纸张分成两个非空部分，因此关键区域保持完整的概率为 $\frac{2}{20}$ ，即 $\frac{1}{10}$ 。对 $998244353$ 取模后输出 $299473306$ 。

在第三个测试用例中，关键区域保持完整的概率为 $\frac{8}{20}$ ，即 $\frac{2}{5}$ 。对 $998244353$ 取模后输出 $199648871$ 。

思路讲解

完全理解隔板法（stars and bars）（插板法应用的特征）

我觉得是类似于这样子思考。

隔板法的思想就是，把 a 插入 d 个空格当中，换为给 a 加上 d-1 个隔板。

AC代码

源代码