Codeforces Round 1136 (Div. 1, Div. 2) Editorial
Разница между en3 и en4, 78255 символ(ов) изменены
Thanks to everyone who participated in this round! I hope you enjoyed the problems! Apologies for the overly simplistic Div2D and the trivial Div1D(and the statements with poor readability). I think that the whole difficulty of Div1D lies in how people hack the solutions of other participants: if nobody hacks, this problem is easier than Div1C, but if somebody hacks, it becomes hard. I will explain this in more detail in the tutorial below.↵
↵
### [problem:2288A]↵
↵
<spoiler summary="Hint 1">↵
The last operation can only be an Attack.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
You can only Charge several times first and then Attack several times.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
If your sequence of operations contains a segment [Attack, several Charges, several Attacks], move the leading Attack behind those Charges. The total damage cannot decrease.↵
↵
Therefore we may assume that all Attacks are performed after all Charges. Then you can enumerate how many Charges are performed at the very beginning, and simulate how many Attacks are needed to defeat the youkai.↵
↵
Depending on the implementation, your time complexity is either $O(x)$ or $O(x\log x)$ per test case.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:399399085]↵
</spoiler>↵
↵
### [problem:2288B1] / [problem:2287A1]↵
↵
<spoiler summary="Hint 1">↵
Use dynamic programming.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288B1]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:399399159]↵
</spoiler>↵
↵
### [problem:2288B2] / [problem:2287A2]↵
↵
<spoiler summary="Hint 1">↵
We need $k$ to take at least $n+1$ different values. What do we need for that?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
In the vast majority of cases the returned $k$ points at a \texttt{+}, and either $k$ is already the end of the string or $k+1$ points at a \texttt{-}.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
A repeated structure \texttt{+-} is useless.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
To make good use of every character, a naive idea is to spread the possible values of $k$ as evenly as possible. For that we should use more \texttt{-} characters.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288B2]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:399399227]↵
</spoiler>↵
↵
### [problem:2288C]↵
↵
<spoiler summary="Hint 1">↵
We only need to track how many attacks a youkai needs before it leaves the field, which is $c_i = \left\lceil \frac{a_i}{x} \right\rceil$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Sort $c$ and ignore the maximum.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288C]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:399399294]↵
</spoiler>↵
↵
### [problem:2288D] / [problem:2287B]↵
↵
<spoiler summary="Hint 1">↵
At least one of the two trains must stop at every station. Why?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
The other train only stops at a prefix and a suffix. Why?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288D]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:399399503]↵
</spoiler>↵
↵
### [problem:2288E] / [problem:2287C]↵
↵
<spoiler summary="Hint 1">↵
It is obvious that we should use bitsets.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
The final time complexity is $O\left(\frac{n_{\max} m_{\max} \log m_{\max}}{w}\right)$, where $w = 64$. Do not worry about TLE: this code runs fast and is completely fine.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288E]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:399399592]↵
</spoiler>↵
↵
### [problem:2287D]↵
↵
<spoiler summary="Hint 1">↵
How would you solve this problem if there were no hacks?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Is there any way to compute the hashes of the length-$\ell$ prefixes of $a_0, a_1, \dots, a_{n-1}$ quickly?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Classic string hashing is great: it supports rolling hashes, but it also makes us fragile when facing attacks.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2287D]↵
↵
PS: This problem accepts using a high-resolution clock as the RNG seed. Among the approaches known today, if you do not use it, you have to use a cryptographic hash (such as SHA-256). Also, banning timers is technically unrealistic, and it would expose the intended solution of this problem.↵
↵
PS: During testing, Codex used **fixed seeds** and **one** RNG-generated weight array, and compared every character naively whenever the hashes were equal. I successfully constructed data that hacks this approach (a 120s TLE), and I proved that even with **four** independent RNGs, this approach is still fragile as long as the seeds are fixed (I constructed a 20s TLE). But I guess that during the Div1 contest nobody will try to hack this approach.↵
</spoiler>↵
↵
<spoiler summary="Code with high-resolution clock">↵
[submission:399399731]↵
</spoiler>↵
↵
<spoiler summary="Code with sha-256">↵
[submission:399399760]↵
</spoiler>↵
↵
### [problem:2287E1]↵
↵
My initial problem only had an $n \le 10^5$ version and an $n \le 500$ version; thanks to [user:Error_Yuan,2026-11-21] for proposing this $n \le 10^4$ version.↵
↵
<spoiler summary="Hint 1">↵
If the two maxima differ, or if they are equal with different multiplicities, the position is already trivial: keep attacking the opponent's maximum, and the outcome is decided by whose maximum is larger and, on a tie, by who owns more copies of it.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
A player has only two useful attack targets: the opponent's maximum value and the opponent's strict second maximum. Attacking anything smaller brings no extra profit.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Both players may play optimally without ever skipping a turn: skipping never turns a lost position into a non-lost one, so every move may be assumed to be a real attack.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2287E1]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:399399865]↵
</spoiler>↵
↵
The idea comes from the power level settings of some fantasy works. In many fantasy works every character has a power level, and the levels differ wildly (for example, Tier 10 is an ordinary human, while Tier 9 is a superhuman). In this setting I created this problem, so that you can see how a battle between two groups should happen in such a fantasy world, and what the best arrangement is if a group wants to defeat another group.↵
↵
### [problem:2287E2]↵
↵
Codex did not pass this problem during testing, which surprised me a lot.↵
↵
Before reading, please go through the hints of [problem:2287E1], but no need read its tutorial, because what follows is completely different.↵
↵
<spoiler summary="Hint 1">↵
Sort the input. You can see that at any moment both players hold a prefix plus $k$ copies of the maximum value. This is already an $O(n^3)$-level DP.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
We focus on the case $k = 0$: at this moment both players hold only a prefix, and we enter a subproblem.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Recall Hint 1 of the easy version: only $O(n)$ subproblems are not trivial.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Every state with $k > 0$ can be derived from the states with $k = 0$, and we only need to find the derivation rule.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2287E2]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:399399973]
~~~~~↵
#include <algorithm>↵
#include <cstdio>↵
 ↵
int main() {↵
    int t;↵
    if (scanf("%d", &t) != 1) return 0;↵
    while (t-- > 0) {↵
        int x;↵
        if (scanf("%d", &x) != 1) return 0;↵
        int best = x;  // attacking x times with no charges always works↵
        for (int a = 0; a <= x; ++a) {↵
            int damage = 0, stacks = a, moves = a;↵
            while (damage < x) {↵
                if (stacks == 0) {  // every remaining attack deals 1 damage↵
                    moves += x - damage;↵
                    break;↵
                }↵
                damage += stacks + 1;↵
                --stacks;↵
                ++moves;↵
            }↵
            best = std::min(best, moves);↵
        }↵
        printf("%d\n", best);↵
    }↵
    return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
### [problem:2288B1] / [problem:2287A1]↵
↵
<spoiler summary="Hint 1">↵
Use dynamic programming.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288B1]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
    int t;↵
    if (scanf("%d", &t) != 1)↵
        return 0;↵
↵
    while (t--) {↵
        int x, y, m;↵
        if (scanf("%d %d %d", &x, &y, &m) != 3)↵
            return 0;↵
↵
        char buf[256];↵
        if (scanf("%255s", buf) != 1)↵
            return 0;↵
        string s(buf);↵
↵
        int n = x + y;↵
        int maxI = n + m + 2;↵
        vector<int> dp(maxI + 2, -1), nd(maxI + 2, -1);↵
        dp[y] = n;↵
↵
        int ans = n;                                    // the empty prefix↵
        for (char ch : s) {↵
            fill(nd.begin(), nd.end(), -1);↵
            for (int i = 0; i <= maxI; ++i) {↵
                int u = dp[i];↵
                if (u < 0)↵
                    continue;↵
                if (ch == '+') {↵
                    if (i >= 1)↵
                        nd[i + 1] = max(nd[i + 1], u + 1);↵
                    else if (u >= 1)↵
                        nd[1] = max(nd[1], u);↵
                } else {↵
                    if (i >= 1)↵
                        nd[i - 1] = max(nd[i - 1], u);↵
                    if (u - i >= 1)↵
                        nd[i] = max(nd[i], u - 1);↵
                }↵
            }↵
            dp.swap(nd);↵
            for (int i = 0; i <= maxI; ++i)↵
                ans = max(ans, dp[i]);↵
        }↵
↵
        printf("%d\n", ans);↵
    }↵
    return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### [problem:2288B2] / [problem:2287A2]↵
↵
<spoiler summary="Hint 1">↵
We need $k$ to take at least $n+1$ different values. What do we need for that?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
In the vast majority of cases the returned $k$ points at a \texttt{+}, and either $k$ is already the end of the string or $k+1$ points at a \texttt{-}.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
A repeated structure \texttt{+-} is useless.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
To make good use of every character, a naive idea is to spread the possible values of $k$ as evenly as possible. For that we should use more \texttt{-} characters.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288B2]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
 ↵
using namespace std;↵
 ↵
int main() {↵
    int t;↵
    if (scanf("%d", &t) != 1)↵
        return 0;↵
 ↵
    string spell = "+";↵
    while ((int)spell.size() < 997)↵
        spell += "--+";↵
 ↵
    while (t--) {↵
        int n;↵
        scanf("%d", &n);↵
 ↵
        printf("%s\n", spell.c_str());↵
        fflush(stdout);↵
 ↵
        int k;↵
        scanf("%d", &k);↵
 ↵
        int y = (k == 0 ? 0 : (k + 2) / 3);↵
        printf("%d\n", n + y);↵
        fflush(stdout);↵
    }↵
    return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### [problem:2288C]↵
↵
<spoiler summary="Hint 1">↵
We only need to track how many attacks a youkai needs before it leaves the field, which is $c_i = \left\lceil \frac{a_i}{x} \right\rceil$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Sort $c$ and ignore the maximum.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288C]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
 ↵
int main() {↵
    ios::sync_with_stdio(false);↵
    cin.tie(nullptr);↵
 ↵
    int T;↵
    cin >> T;↵
 ↵
    while (T--) {↵
        int n;↵
        long long x;↵
        cin >> n >> x;↵
 ↵
        vector<long long> h(n);↵
 ↵
        for (int i = 0; i < n; i++) {↵
            long long a;↵
            cin >> a;↵
            h[i] = (a + x - 1) / x; // hits needed to defeat this youkai↵
        }↵
 ↵
        sort(h.begin(), h.end());↵
 ↵
        long long ans = 0;↵
 ↵
        // Leave the largest h as the final surviving youkai.↵
        for (int i = 0; i < n - 1; i++) {↵
            ans = max(ans, h[i] - (long long)(i + 1));↵
        }↵
 ↵
        cout << ans << '\n';↵
    }↵
 ↵
    return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### [problem:2288D] / [problem:2287B]↵
↵
<spoiler summary="Hint 1">↵
At least one of the two trains must stop at every station. Why?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
The other train only stops at a prefix and a suffix. Why?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288D]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
template<typename T1> istream& operator>>(istream& cin, vector<T1>& a) { for (auto& x : a) cin >> x; return cin; }↵
↵
void Solve() {↵
    int n;↵
    cin >> n;↵
    vector<ll>a(n);↵
    cin >> a;↵
    auto ck = [&](ll x)->bool {↵
        ll tmp = 0;↵
        vector<int>stop(n);↵
        for (int i = 0; i < n; i++) {↵
            tmp += a[i];↵
            if (tmp > x)stop[i] = 1;↵
        }↵
        tmp = 0;↵
        for (int i = n - 1; i >= 0; i--) {↵
            tmp += a[i];↵
            if (tmp > x)stop[i] = 1;↵
        }↵
        tmp = 0;↵
        for (int i = 0; i < n; i++) {↵
            if (stop[i])tmp += a[i];↵
        }↵
        return tmp > x;↵
        };↵
    ll res = 0;↵
    ll tmp = 1ll << 50;↵
    while (tmp) {↵
        if (ck(res + tmp))res += tmp;↵
        tmp >>= 1;↵
    }↵
    cout << res + 1 << endl;↵
}↵
int main() {↵
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
    int T = 1;↵
    cin >> T;↵
    while (T--) Solve();↵
    return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### [problem:2288E] / [problem:2287C]↵
↵
<spoiler summary="Hint 1">↵
It is obvious that we should use bitsets.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
The final time complexity is $O\left(\frac{n_{\max} m_{\max} \log m_{\max}}{w}\right)$, where $w = 64$. Do not worry about TLE: this code runs fast and is completely fine.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2288E]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define all(x) (x).begin(),(x).end()↵
#define N 50010↵
↵
int pri[N];↵
int mu[N];↵
↵
void Init() {↵
    mu[1] = 1;↵
    vector<int>primes;↵
    for (int x = 2; x < N; ++x) {↵
        if (!pri[x]) {↵
            primes.push_back(x);↵
            mu[x] = -1;↵
        }↵
        for (int p : primes) {↵
            if (x * p >= N) break;↵
            pri[x * p] = true;↵
            if (x % p == 0) {↵
                mu[x * p] = 0;↵
                break;↵
            }↵
            else {↵
                mu[x * p] = -mu[x];↵
            }↵
        }↵
    }↵
}↵
↵
struct que↵
{↵
    int id;↵
    int n, m;↵
    bool operator<(const que& o)const {↵
        if (o.m != m)return m < o.m;↵
        return id < o.id;↵
    }↵
};↵
↵
void Solve() {↵
    int q;↵
    cin >> q;↵
    vector<que>t(q);↵
    vector<int>ans(q);↵
    for (int i = 0; i < q; i++) {↵
        cin >> t[i].n >> t[i].m;↵
        t[i].id = i;↵
    }↵
    sort(all(t));↵
    int p = 0;↵
    int m = 50000;↵
    vector<bitset<50000>>dp(m + 1);↵
    dp[1][0] = 1;↵
    bitset<50000>res;↵
    res[0] = 1;↵
    while (p < q && t[p].m == 1) {↵
        ans[t[p].id] = res[t[p].n - 1];↵
        p++;↵
    }↵
    dp[1] <<= 1;↵
    for (int j = 2; j <= m; j++) {↵
        bitset<50000>tmp;↵
        for (int i = 1; i * i <= j; i++) {↵
            if (j % i)continue;↵
            if (mu[i]) {↵
                tmp ^= dp[i];↵
            }↵
            if (j / i != i) {↵
                if (mu[j / i]) {↵
                    tmp ^= dp[j / i];↵
                }↵
            }↵
        }↵
        tmp[0] = 1;↵
        res ^= tmp;↵
        while (p < q && t[p].m == j) {↵
            ans[t[p].id] = res[t[p].n - 1];↵
            p++;↵
        }↵
        tmp <<= 1;↵
        for (int i = 1; i * i <= j; i++) {↵
            if (j % i)continue;↵
            dp[i] ^= tmp;↵
            if (j / i != i) {↵
                dp[j / i] ^= tmp;↵
            }↵
        }↵
    }↵
    for (auto& u : ans)cout << u << endl;↵
}↵
↵
int main() {↵
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
    Init();↵
    Solve();↵
    return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### [problem:2287D]↵
↵
<spoiler summary="Hint 1">↵
How would you solve this problem if there were no hacks?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Is there any way to compute the hashes of the length-$\ell$ prefixes of $a_0, a_1, \dots, a_{n-1}$ quickly?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Classic string hashing is great: it supports rolling hashes, but it also makes us fragile when facing attacks.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2287D]↵
↵
PS: This problem accepts using a high-resolution clock as the RNG seed. Among the approaches known today, if you do not use it, you have to use a cryptographic hash (such as SHA-256). Also, banning timers is technically unrealistic, and it would expose the intended solution of this problem.↵
↵
PS: During testing, Codex used **fixed seeds** and **one** RNG-generated weight array, and compared every character naively whenever the hashes were equal. I successfully constructed data that hacks this approach (a 120s TLE), and I proved that even with **four** independent RNGs, this approach is still fragile as long as the seeds are fixed (I constructed a 20s TLE). But I guess that during the Div1 contest nobody will try to hack this approach.↵
</spoiler>↵
↵
<spoiler summary="Code with high-resolution clock">↵
↵
~~~~~↵
// Generated by OpenAI Codex (AI)↵
#include <bits/stdc++.h>↵
using namespace std;↵
 ↵
using ll = long long;↵
const int MOD = 998244353;↵
 ↵
int pw(int a, int b) {↵
    int ans = 1;↵
    while (b) {↵
        if (b & 1) ans = (ll)ans * a % MOD;↵
        a = (ll)a * a % MOD;↵
        b >>= 1;↵
    }↵
    return ans;↵
}↵
 ↵
struct NTT {↵
    int n;↵
    vector<int> rev, roots;↵
 ↵
    NTT(int n) : n(n), rev(n), roots(n) {↵
        for (int i = 1; i < n; i++) {↵
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? n >> 1 : 0);↵
        }↵
        for (int len = 1; len < n; len <<= 1) {↵
            int w = pw(3, (MOD - 1) / (len << 1));↵
            roots[len] = 1;↵
            for (int j = 1; j < len; j++) {↵
                roots[len + j] = (ll)roots[len + j - 1] * w % MOD;↵
            }↵
        }↵
    }↵
 ↵
    void transform(vector<int>& a, bool inverse = false) {↵
        for (int i = 0; i < n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);↵
        for (int len = 1; len < n; len <<= 1) {↵
            for (int i = 0; i < n; i += len << 1) {↵
                for (int j = 0; j < len; j++) {↵
                    int x = a[i + j];↵
                    int y = (ll)a[i + j + len] * roots[len + j] % MOD;↵
                    a[i + j] = x + y;↵
                    if (a[i + j] >= MOD) a[i + j] -= MOD;↵
                    a[i + j + len] = x - y;↵
                    if (a[i + j + len] < 0) a[i + j + len] += MOD;↵
                }↵
            }↵
        }↵
        if (inverse) {↵
            reverse(a.begin() + 1, a.end());↵
            int inv = pw(n, MOD - 2);↵
            for (int& x : a) x = (ll)x * inv % MOD;↵
        }↵
    }↵
};↵
 ↵
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());↵
 ↵
void solve() {↵
    int n;↵
    string s;↵
    cin >> n >> s;↵
    vector<int> p(n);↵
    for (int& x : p) cin >> x, --x;↵
 ↵
    vector<int> pi(n);↵
    for (int i = 1; i < n; i++) {↵
        int j = pi[i - 1];↵
        while (j && s[i] != s[j]) j = pi[j - 1];↵
        if (s[i] == s[j]) j++;↵
        pi[i] = j;↵
    }↵
    if (n % (n - pi.back()) == 0 && pi.back()) {↵
        cout << n << '\n';↵
        return;↵
    }↵
 ↵
    int len = 1;↵
    while (len < 2 * n - 1) len <<= 1;↵
    NTT ntt(len);↵
    vector<int> spectrum(len), weight(n), work(len);↵
    for (int i = 0; i < n; i++) {↵
        spectrum[i] = s[i] - 'a';↵
        weight[i] = uniform_int_distribution<int>(1, MOD - 1)(rng);↵
    }↵
    ntt.transform(spectrum);↵
    s += s;↵
    vector<pair<int, int>> hashes(n);↵
 ↵
    auto check = [&](int k) {↵
        fill(work.begin(), work.end(), 0);↵
        for (int i = 0; i < k; i++) work[(n - p[i]) % n] = weight[i];↵
        ntt.transform(work);↵
        for (int i = 0; i < len; i++) work[i] = (ll)work[i] * spectrum[i] % MOD;↵
        ntt.transform(work, true);↵
        for (int i = 0; i < n; i++) {↵
            int value = work[i];↵
            if (i + n < 2 * n - 1) {↵
                value += work[i + n];↵
                if (value >= MOD) value -= MOD;↵
            }↵
            hashes[i] = {value, i};↵
        }↵
        sort(hashes.begin(), hashes.end());↵
        for (int l = 0; l < n; ) {↵
            int r = l + 1;↵
            while (r < n && hashes[r].first == hashes[l].first) r++;↵
            for (int i = l; i < r; i++) {↵
                for (int j = l; j < i; j++) {↵
                    int u = hashes[i].second, v = hashes[j].second;↵
                    bool same = true;↵
                    for (int h = 0; h < k; h++) {↵
                        if (s[u + p[h]] != s[v + p[h]]) {↵
                            same = false;↵
                            break;↵
                        }↵
                    }↵
                    if (same) return true;↵
                }↵
            }↵
            l = r;↵
        }↵
        return false;↵
    };↵
 ↵
    int lo = 0, hi = n;↵
    while (hi - lo > 1) {↵
        int mid = (lo + hi) >> 1;↵
        if (check(mid)) lo = mid;↵
        else hi = mid;↵
    }↵
    cout << lo << '\n';↵
}↵
 ↵
int main() {↵
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);↵
    int t;↵
    cin >> t;↵
    while (t--) solve();↵
    return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Code with sha-256">↵
↵
~~~~~↵
//I must have missed the evolution memo.↵
//In case I never coding, good afternoon, good evening, and good night.↵
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING↵
#define _SILENCE_CXX20_CISO646_REMOVED_WARNING↵
#define _CRT_SECURE_NO_WARNINGS↵
#pragma warning(disable : 4700)↵
#include "bits/stdc++.h"↵
#include <random>↵
#include <array>↵
#include <chrono>↵
#if 0↵
#include "atcoder/all"↵
using namespace atcoder;↵
#endif↵
using namespace std;↵
template<typename T1, typename T2> istream& operator>>(istream& cin, pair<T1, T2>& a) { return cin >> a.first >> a.second; }↵
template<typename T1> istream& operator>>(istream& cin, vector<T1>& a) { for (auto& x : a) cin >> x; return cin; }↵
template<typename T1> istream& operator>>(istream& cin, valarray<T1>& a) { for (auto& x : a) cin >> x; return cin; }↵
template<typename T1, typename T2> ostream& operator<<(ostream& cout, const pair<T1, T2>& a) { return cout << a.first << ' ' << a.second; }↵
template<typename T1, typename T2> ostream& operator<<(ostream& cout, const vector<pair<T1, T2>>& a) { for (auto& x : a) cout << x << '\n'; return cout; }↵
template<typename T1> ostream& operator<<(ostream& cout, const vector<T1>& a) { int n = a.size(); if (!n) return cout; cout << a[0]; for (int i = 1; i < n; i++) cout << ' ' << a[i]; return cout; }↵
template<typename T1, typename T2> bool cmin(T1& x, const T2& y) { if (y < x) { x = y; return 1; } return 0; }↵
template<typename T1, typename T2> bool cmax(T1& x, const T2& y) { if (x < y) { x = y; return 1; } return 0; }↵
template<typename T1> vector<T1> range(T1 l, T1 r, T1 step = 1) { assert(step > 0); int n = (r - l + step - 1) / step, i; vector<T1> res(n); for (i = 0; i < n; i++) res[i] = l + step * i; return res; }↵
template<typename T1> basic_string<T1> operator*(const basic_string<T1>& s, int m) { auto r = s; m *= s.size(); r.resize(m); for (int i = s.size(); i < m; i++) r[i] = r[i - s.size()]; return r; }↵
#if !defined(ONLINE_JUDGE)&&defined(LOCAL)↵
#include "my_header\debug.h"↵
#else↵
#define dbg(...) ;↵
#define dbgn(...) ;↵
#endif↵
typedef unsigned int ui;↵
typedef double db;↵
typedef long long ll;↵
typedef unsigned long long ull;↵
#define all(x) (x).begin(),(x).end()↵
#define Endl endl↵
#define THREADCNT 8↵
#define MY_NAME "LNight"↵
#define NAN 0.1217728619↵
#define small_queue(name, ...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>name↵
#define small_queue_type(...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>↵
 ↵
 ↵
namespace atcoder {↵
 ↵
    namespace internal {↵
 ↵
#ifndef _MSC_VER↵
        template <class T>↵
        using is_signed_int128 =↵
            typename std::conditional<std::is_same<T, __int128_t>::value ||↵
            std::is_same<T, __int128>::value,↵
            std::true_type,↵
            std::false_type>::type;↵
 ↵
        template <class T>↵
        using is_unsigned_int128 =↵
            typename std::conditional<std::is_same<T, __uint128_t>::value ||↵
            std::is_same<T, unsigned __int128>::value,↵
            std::true_type,↵
            std::false_type>::type;↵
 ↵
        template <class T>↵
        using make_unsigned_int128 =↵
            typename std::conditional<std::is_same<T, __int128_t>::value,↵
            __uint128_t,↵
            unsigned __int128>;↵
 ↵
        template <class T>↵
        using is_integral = typename std::conditional<std::is_integral<T>::value ||↵
            is_signed_int128<T>::value ||↵
            is_unsigned_int128<T>::value,↵
            std::true_type,↵
            std::false_type>::type;↵
 ↵
        template <class T>↵
        using is_signed_int = typename std::conditional<(is_integral<T>::value&&↵
            std::is_signed<T>::value) ||↵
            is_signed_int128<T>::value,↵
            std::true_type,↵
            std::false_type>::type;↵
 ↵
        template <class T>↵
        using is_unsigned_int =↵
            typename std::conditional<(is_integral<T>::value&&↵
                std::is_unsigned<T>::value) ||↵
            is_unsigned_int128<T>::value,↵
            std::true_type,↵
            std::false_type>::type;↵
 ↵
        template <class T>↵
        using to_unsigned = typename std::conditional<↵
            is_signed_int128<T>::value,↵
            make_unsigned_int128<T>,↵
            typename std::conditional<std::is_signed<T>::value,↵
            std::make_unsigned<T>,↵
            std::common_type<T>>::type>::type;↵
 ↵
#else↵
 ↵
        template <class T> using is_integral = typename std::is_integral<T>;↵
 ↵
        template <class T>↵
        using is_signed_int =↵
            typename std::conditional<is_integral<T>::value&& std::is_signed<T>::value,↵
            std::true_type,↵
            std::false_type>::type;↵
 ↵
        template <class T>↵
        using is_unsigned_int =↵
            typename std::conditional<is_integral<T>::value&&↵
            std::is_unsigned<T>::value,↵
            std::true_type,↵
            std::false_type>::type;↵
 ↵
        template <class T>↵
        using to_unsigned = typename std::conditional<is_signed_int<T>::value,↵
            std::make_unsigned<T>,↵
            std::common_type<T>>::type;↵
 ↵
#endif↵
 ↵
        template <class T>↵
        using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;↵
 ↵
        template <class T>↵
        using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;↵
 ↵
        template <class T> using to_unsigned_t = typename to_unsigned<T>::type;↵
 ↵
    }  // namespace internal↵
 ↵
}  // namespace atcoder↵
 ↵
namespace atcoder {↵
 ↵
    namespace internal {↵
 ↵
        // @param m `1 <= m`↵
        // @return x mod m↵
        constexpr long long safe_mod(long long x, long long m) {↵
            x %= m;↵
            if (x < 0) x += m;↵
            return x;↵
        }↵
 ↵
        // Fast modular multiplication by barrett reduction↵
        // Reference: https://en.wikipedia.org/wiki/Barrett_reduction↵
        // NOTE: reconsider after Ice Lake↵
        struct barrett {↵
            unsigned int _m;↵
            unsigned long long im;↵
 ↵
            // @param m `1 <= m`↵
            explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}↵
 ↵
            // @return m↵
            unsigned int umod() const { return _m; }↵
 ↵
            // @param a `0 <= a < m`↵
            // @param b `0 <= b < m`↵
            // @return `a * b % m`↵
            unsigned int mul(unsigned int a, unsigned int b) const {↵
                // [1] m = 1↵
                // a = b = im = 0, so okay↵
 ↵
                // [2] m >= 2↵
                // im = ceil(2^64 / m)↵
                // -> im * m = 2^64 + r (0 <= r < m)↵
                // let z = a*b = c*m + d (0 <= c, d < m)↵
                // a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im↵
                // c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2↵
                // ((ab * im) >> 64) == c or c + 1↵
                unsigned long long z = a;↵
                z *= b;↵
#ifdef _MSC_VER↵
                unsigned long long x;↵
                _umul128(z, im, &x);↵
#else↵
                unsigned long long x =↵
                    (unsigned long long)(((unsigned __int128)(z)*im) >> 64);↵
#endif↵
                unsigned long long y = x * _m;↵
                return (unsigned int)(z - y + (z < y ? _m : 0));↵
            }↵
        };↵
 ↵
        // @param n `0 <= n`↵
        // @param m `1 <= m`↵
        // @return `(x ** n) % m`↵
        constexpr long long pow_mod_constexpr(long long x, long long n, int m) {↵
            if (m == 1) return 0;↵
            unsigned int _m = (unsigned int)(m);↵
            unsigned long long r = 1;↵
            unsigned long long y = safe_mod(x, m);↵
            while (n) {↵
                if (n & 1) r = (r * y) % _m;↵
                y = (y * y) % _m;↵
                n >>= 1;↵
            }↵
            return r;↵
        }↵
 ↵
        // Reference:↵
        // M. Forisek and J. Jancina,↵
        // Fast Primality Testing for Integers That Fit into a Machine Word↵
        // @param n `0 <= n`↵
        constexpr bool is_prime_constexpr(int n) {↵
            if (n <= 1) return false;↵
            if (n == 2 || n == 7 || n == 61) return true;↵
            if (n % 2 == 0) return false;↵
            long long d = n - 1;↵
            while (d % 2 == 0) d /= 2;↵
            constexpr long long bases[3] = { 2, 7, 61 };↵
            for (long long a : bases) {↵
                long long t = d;↵
                long long y = pow_mod_constexpr(a, t, n);↵
                while (t != n - 1 && y != 1 && y != n - 1) {↵
                    y = y * y % n;↵
                    t <<= 1;↵
                }↵
                if (y != n - 1 && t % 2 == 0) {↵
                    return false;↵
                }↵
            }↵
            return true;↵
        }↵
        template <int n> constexpr bool is_prime = is_prime_constexpr(n);↵
 ↵
        // @param b `1 <= b`↵
        // @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g↵
        constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {↵
            a = safe_mod(a, b);↵
            if (a == 0) return { b, 0 };↵
 ↵
            // Contracts:↵
            // [1] s - m0 * a = 0 (mod b)↵
            // [2] t - m1 * a = 0 (mod b)↵
            // [3] s * |m1| + t * |m0| <= b↵
            long long s = b, t = a;↵
            long long m0 = 0, m1 = 1;↵
 ↵
            while (t) {↵
                long long u = s / t;↵
                s -= t * u;↵
                m0 -= m1 * u;  // |m1 * u| <= |m1| * s <= b↵
 ↵
                // [3]:↵
                // (s - t * u) * |m1| + t * |m0 - m1 * u|↵
                // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)↵
                // = s * |m1| + t * |m0| <= b↵
 ↵
                auto tmp = s;↵
                s = t;↵
                t = tmp;↵
                tmp = m0;↵
                m0 = m1;↵
                m1 = tmp;↵
            }↵
            // by [3]: |m0| <= b/g↵
            // by g != b: |m0| < b/g↵
            if (m0 < 0) m0 += b / s;↵
            return { s, m0 };↵
        }↵
 ↵
        // Compile time primitive root↵
        // @param m must be prime↵
        // @return primitive root (and minimum in now)↵
        constexpr int primitive_root_constexpr(int m) {↵
            if (m == 2) return 1;↵
            if (m == 167772161) return 3;↵
            if (m == 469762049) return 3;↵
            if (m == 754974721) return 11;↵
            if (m == 998244353) return 3;↵
            int divs[20] = {};↵
            divs[0] = 2;↵
            int cnt = 1;↵
            int x = (m - 1) / 2;↵
            while (x % 2 == 0) x /= 2;↵
            for (int i = 3; (long long)(i)*i <= x; i += 2) {↵
                if (x % i == 0) {↵
                    divs[cnt++] = i;↵
                    while (x % i == 0) {↵
                        x /= i;↵
                    }↵
                }↵
            }↵
            if (x > 1) {↵
                divs[cnt++] = x;↵
            }↵
            for (int g = 2;; g++) {↵
                bool ok = true;↵
                for (int i = 0; i < cnt; i++) {↵
                    if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {↵
                        ok = false;↵
                        break;↵
                    }↵
                }↵
                if (ok) return g;↵
            }↵
        }↵
        template <int m> constexpr int primitive_root = primitive_root_constexpr(m);↵
 ↵
        // @param n `n < 2^32`↵
        // @param m `1 <= m < 2^32`↵
        // @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)↵
        unsigned long long floor_sum_unsigned(unsigned long long n,↵
            unsigned long long m,↵
            unsigned long long a,↵
            unsigned long long b) {↵
            unsigned long long ans = 0;↵
            while (true) {↵
                if (a >= m) {↵
                    ans += n * (n - 1) / 2 * (a / m);↵
                    a %= m;↵
                }↵
                if (b >= m) {↵
                    ans += n * (b / m);↵
                    b %= m;↵
                }↵
 ↵
                unsigned long long y_max = a * n + b;↵
                if (y_max < m) break;↵
                // y_max < m * (n + 1)↵
                // floor(y_max / m) <= n↵
                n = (unsigned long long)(y_max / m);↵
                b = (unsigned long long)(y_max % m);↵
                std::swap(m, a);↵
            }↵
            return ans;↵
        }↵
 ↵
    }  // namespace internal↵
 ↵
}  // namespace atcoder↵
 ↵
namespace atcoder {↵
 ↵
    namespace internal {↵
 ↵
        struct modint_base {};↵
        struct static_modint_base : modint_base {};↵
 ↵
        template <class T> using is_modint = std::is_base_of<modint_base, T>;↵
        template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;↵
 ↵
    }  // namespace internal↵
 ↵
    template <int m, std::enable_if_t<(1 <= m)>* = nullptr>↵
    struct static_modint : internal::static_modint_base {↵
        using mint = static_modint;↵
 ↵
    public:↵
        static constexpr int mod() { return m; }↵
        static mint raw(int v) {↵
            mint x;↵
            x._v = v;↵
            return x;↵
        }↵
 ↵
        static_modint() : _v(0) {}↵
        template <class T, internal::is_signed_int_t<T>* = nullptr>↵
        static_modint(T v) {↵
            long long x = (long long)(v % (long long)(umod()));↵
            if (x < 0) x += umod();↵
            _v = (unsigned int)(x);↵
        }↵
        template <class T, internal::is_unsigned_int_t<T>* = nullptr>↵
        static_modint(T v) {↵
            _v = (unsigned int)(v % umod());↵
        }↵
 ↵
        unsigned int val() const { return _v; }↵
 ↵
        mint& operator++() {↵
            _v++;↵
            if (_v == umod()) _v = 0;↵
            return *this;↵
        }↵
        mint& operator--() {↵
            if (_v == 0) _v = umod();↵
            _v--;↵
            return *this;↵
        }↵
        mint operator++(int) {↵
            mint result = *this;↵
            ++*this;↵
            return result;↵
        }↵
        mint operator--(int) {↵
            mint result = *this;↵
            --*this;↵
            return result;↵
        }↵
 ↵
        mint& operator+=(const mint& rhs) {↵
            _v += rhs._v;↵
            if (_v >= umod()) _v -= umod();↵
            return *this;↵
        }↵
        mint& operator-=(const mint& rhs) {↵
            _v -= rhs._v;↵
            if (_v >= umod()) _v += umod();↵
            return *this;↵
        }↵
        mint& operator*=(const mint& rhs) {↵
            unsigned long long z = _v;↵
            z *= rhs._v;↵
            _v = (unsigned int)(z % umod());↵
            return *this;↵
        }↵
        mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }↵
 ↵
        mint operator+() const { return *this; }↵
        mint operator-() const { return mint() - *this; }↵
 ↵
        mint pow(long long n) const {↵
            assert(0 <= n);↵
            mint x = *this, r = 1;↵
            while (n) {↵
                if (n & 1) r *= x;↵
                x *= x;↵
                n >>= 1;↵
            }↵
            return r;↵
        }↵
        mint inv() const {↵
            if (prime) {↵
                assert(_v);↵
                return pow(umod() - 2);↵
            }↵
            else {↵
                auto eg = internal::inv_gcd(_v, m);↵
                assert(eg.first == 1);↵
                return eg.second;↵
            }↵
        }↵
 ↵
        friend mint operator+(const mint& lhs, const mint& rhs) {↵
            return mint(lhs) += rhs;↵
        }↵
        friend mint operator-(const mint& lhs, const mint& rhs) {↵
            return mint(lhs) -= rhs;↵
        }↵
        friend mint operator*(const mint& lhs, const mint& rhs) {↵
            return mint(lhs) *= rhs;↵
        }↵
        friend mint operator/(const mint& lhs, const mint& rhs) {↵
            return mint(lhs) /= rhs;↵
        }↵
        friend bool operator==(const mint& lhs, const mint& rhs) {↵
            return lhs._v == rhs._v;↵
        }↵
        friend bool operator!=(const mint& lhs, const mint& rhs) {↵
            return lhs._v != rhs._v;↵
        }↵
 ↵
    private:↵
        unsigned int _v;↵
        static constexpr unsigned int umod() { return m; }↵
        static constexpr bool prime = internal::is_prime<m>;↵
    };↵
 ↵
    template <int id> struct dynamic_modint : internal::modint_base {↵
        using mint = dynamic_modint;↵
 ↵
    public:↵
        static int mod() { return (int)(bt.umod()); }↵
        static void set_mod(int m) {↵
            assert(1 <= m);↵
            bt = internal::barrett(m);↵
        }↵
        static mint raw(int v) {↵
            mint x;↵
            x._v = v;↵
            return x;↵
        }↵
 ↵
        dynamic_modint() : _v(0) {}↵
        template <class T, internal::is_signed_int_t<T>* = nullptr>↵
        dynamic_modint(T v) {↵
            long long x = (long long)(v % (long long)(mod()));↵
            if (x < 0) x += mod();↵
            _v = (unsigned int)(x);↵
        }↵
        template <class T, internal::is_unsigned_int_t<T>* = nullptr>↵
        dynamic_modint(T v) {↵
            _v = (unsigned int)(v % mod());↵
        }↵
 ↵
        unsigned int val() const { return _v; }↵
 ↵
        mint& operator++() {↵
            _v++;↵
            if (_v == umod()) _v = 0;↵
            return *this;↵
        }↵
        mint& operator--() {↵
            if (_v == 0) _v = umod();↵
            _v--;↵
            return *this;↵
        }↵
        mint operator++(int) {↵
            mint result = *this;↵
            ++*this;↵
            return result;↵
        }↵
        mint operator--(int) {↵
            mint result = *this;↵
            --*this;↵
            return result;↵
        }↵
 ↵
        mint& operator+=(const mint& rhs) {↵
            _v += rhs._v;↵
            if (_v >= umod()) _v -= umod();↵
            return *this;↵
        }↵
        mint& operator-=(const mint& rhs) {↵
            _v += mod() - rhs._v;↵
            if (_v >= umod()) _v -= umod();↵
            return *this;↵
        }↵
        mint& operator*=(const mint& rhs) {↵
            _v = bt.mul(_v, rhs._v);↵
            return *this;↵
        }↵
        mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }↵
 ↵
        mint operator+() const { return *this; }↵
        mint operator-() const { return mint() - *this; }↵
 ↵
        mint pow(long long n) const {↵
            assert(0 <= n);↵
            mint x = *this, r = 1;↵
            while (n) {↵
                if (n & 1) r *= x;↵
                x *= x;↵
                n >>= 1;↵
            }↵
            return r;↵
        }↵
        mint inv() const {↵
            auto eg = internal::inv_gcd(_v, mod());↵
            assert(eg.first == 1);↵
            return eg.second;↵
        }↵
 ↵
        friend mint operator+(const mint& lhs, const mint& rhs) {↵
            return mint(lhs) += rhs;↵
        }↵
        friend mint operator-(const mint& lhs, const mint& rhs) {↵
            return mint(lhs) -= rhs;↵
        }↵
        friend mint operator*(const mint& lhs, const mint& rhs) {↵
            return mint(lhs) *= rhs;↵
        }↵
        friend mint operator/(const mint& lhs, const mint& rhs) {↵
            return mint(lhs) /= rhs;↵
        }↵
        friend bool operator==(const mint& lhs, const mint& rhs) {↵
            return lhs._v == rhs._v;↵
        }↵
        friend bool operator!=(const mint& lhs, const mint& rhs) {↵
            return lhs._v != rhs._v;↵
        }↵
 ↵
    private:↵
        unsigned int _v;↵
        static internal::barrett bt;↵
        static unsigned int umod() { return bt.umod(); }↵
    };↵
    template <int id> internal::barrett dynamic_modint<id>::bt(998244353);↵
 ↵
    using modint998244353 = static_modint<998244353>;↵
    using modint1000000007 = static_modint<1000000007>;↵
    using modint = dynamic_modint<-1>;↵
 ↵
    namespace internal {↵
 ↵
        template <class T>↵
        using is_static_modint = std::is_base_of<internal::static_modint_base, T>;↵
 ↵
        template <class T>↵
        using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;↵
 ↵
        template <class> struct is_dynamic_modint : public std::false_type {};↵
        template <int id>↵
        struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};↵
 ↵
        template <class T>↵
        using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;↵
 ↵
    }  // namespace internal↵
 ↵
}  // namespace atcoder↵
 ↵
namespace atcoder {↵
 ↵
    namespace internal {↵
 ↵
#if __cplusplus >= 202002L↵
 ↵
        using std::bit_ceil;↵
 ↵
#else↵
 ↵
        // @return same with std::bit::bit_ceil↵
        unsigned int bit_ceil(unsigned int n) {↵
            unsigned int x = 1;↵
            while (x < (unsigned int)(n)) x *= 2;↵
            return x;↵
        }↵
 ↵
#endif↵
 ↵
        // @param n `1 <= n`↵
        // @return same with std::bit::countr_zero↵
        int countr_zero(unsigned int n) {↵
#ifdef _MSC_VER↵
            unsigned long index;↵
            _BitScanForward(&index, n);↵
            return index;↵
#else↵
            return __builtin_ctz(n);↵
#endif↵
        }↵
 ↵
        // @param n `1 <= n`↵
        // @return same with std::bit::countr_zero↵
        constexpr int countr_zero_constexpr(unsigned int n) {↵
            int x = 0;↵
            while (!(n & (1 << x))) x++;↵
            return x;↵
        }↵
 ↵
    }  // namespace internal↵
 ↵
}  // namespace atcoder↵
 ↵
namespace atcoder {↵
 ↵
    namespace internal {↵
 ↵
        template <class mint,↵
            int g = internal::primitive_root<mint::mod()>,↵
            internal::is_static_modint_t<mint>* = nullptr>↵
        struct fft_info {↵
            static constexpr int rank2 = countr_zero_constexpr(mint::mod() - 1);↵
            std::array<mint, rank2 + 1> root;   // root[i]^(2^i) == 1↵
            std::array<mint, rank2 + 1> iroot;  // root[i] * iroot[i] == 1↵
 ↵
            std::array<mint, std::max(0, rank2 - 2 + 1)> rate2;↵
            std::array<mint, std::max(0, rank2 - 2 + 1)> irate2;↵
 ↵
            std::array<mint, std::max(0, rank2 - 3 + 1)> rate3;↵
            std::array<mint, std::max(0, rank2 - 3 + 1)> irate3;↵
 ↵
            fft_info() {↵
                root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);↵
                iroot[rank2] = root[rank2].inv();↵
                for (int i = rank2 - 1; i >= 0; i--) {↵
                    root[i] = root[i + 1] * root[i + 1];↵
                    iroot[i] = iroot[i + 1] * iroot[i + 1];↵
                }↵
 ↵
                {↵
                    mint prod = 1, iprod = 1;↵
                    for (int i = 0; i <= rank2 - 2; i++) {↵
                        rate2[i] = root[i + 2] * prod;↵
                        irate2[i] = iroot[i + 2] * iprod;↵
                        prod *= iroot[i + 2];↵
                        iprod *= root[i + 2];↵
                    }↵
                }↵
                {↵
                    mint prod = 1, iprod = 1;↵
                    for (int i = 0; i <= rank2 - 3; i++) {↵
                        rate3[i] = root[i + 3] * prod;↵
                        irate3[i] = iroot[i + 3] * iprod;↵
                        prod *= iroot[i + 3];↵
                        iprod *= root[i + 3];↵
                    }↵
                }↵
            }↵
        };↵
 ↵
        template <class mint, internal::is_static_modint_t<mint>* = nullptr>↵
        void butterfly(std::vector<mint>& a) {↵
            int n = int(a.size());↵
            int h = internal::countr_zero((unsigned int)n);↵
 ↵
            static const fft_info<mint> info;↵
 ↵
            int len = 0;  // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed↵
            while (len < h) {↵
                if (h - len == 1) {↵
                    int p = 1 << (h - len - 1);↵
                    mint rot = 1;↵
                    for (int s = 0; s < (1 << len); s++) {↵
                        int offset = s << (h - len);↵
                        for (int i = 0; i < p; i++) {↵
                            auto l = a[i + offset];↵
                            auto r = a[i + offset + p] * rot;↵
                            a[i + offset] = l + r;↵
                            a[i + offset + p] = l - r;↵
                        }↵
                        if (s + 1 != (1 << len))↵
                            rot *= info.rate2[countr_zero(~(unsigned int)(s))];↵
                    }↵
                    len++;↵
                }↵
                else {↵
                    // 4-base↵
                    int p = 1 << (h - len - 2);↵
                    mint rot = 1, imag = info.root[2];↵
                    for (int s = 0; s < (1 << len); s++) {↵
                        mint rot2 = rot * rot;↵
                        mint rot3 = rot2 * rot;↵
                        int offset = s << (h - len);↵
                        for (int i = 0; i < p; i++) {↵
                            auto mod2 = 1ULL * mint::mod() * mint::mod();↵
                            auto a0 = 1ULL * a[i + offset].val();↵
                            auto a1 = 1ULL * a[i + offset + p].val() * rot.val();↵
                            auto a2 = 1ULL * a[i + offset + 2 * p].val() * rot2.val();↵
                            auto a3 = 1ULL * a[i + offset + 3 * p].val() * rot3.val();↵
                            auto a1na3imag =↵
                                1ULL * mint(a1 + mod2 - a3).val() * imag.val();↵
                            auto na2 = mod2 - a2;↵
                            a[i + offset] = a0 + a2 + a1 + a3;↵
                            a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));↵
                            a[i + offset + 2 * p] = a0 + na2 + a1na3imag;↵
                            a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);↵
                        }↵
                        if (s + 1 != (1 << len))↵
                            rot *= info.rate3[countr_zero(~(unsigned int)(s))];↵
                    }↵
                    len += 2;↵
                }↵
            }↵
        }↵
 ↵
        template <class mint, internal::is_static_modint_t<mint>* = nullptr>↵
        void butterfly_inv(std::vector<mint>& a) {↵
            int n = int(a.size());↵
            int h = internal::countr_zero((unsigned int)n);↵
 ↵
            static const fft_info<mint> info;↵
 ↵
            int len = h;  // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed↵
            while (len) {↵
                if (len == 1) {↵
                    int p = 1 << (h - len);↵
                    mint irot = 1;↵
                    for (int s = 0; s < (1 << (len - 1)); s++) {↵
                        int offset = s << (h - len + 1);↵
                        for (int i = 0; i < p; i++) {↵
                            auto l = a[i + offset];↵
                            auto r = a[i + offset + p];↵
                            a[i + offset] = l + r;↵
                            a[i + offset + p] =↵
                                (unsigned long long)(mint::mod() + l.val() - r.val()) *↵
                                irot.val();↵
                            ;↵
                        }↵
                        if (s + 1 != (1 << (len - 1)))↵
                            irot *= info.irate2[countr_zero(~(unsigned int)(s))];↵
                    }↵
                    len--;↵
                }↵
                else {↵
                    // 4-base↵
                    int p = 1 << (h - len);↵
                    mint irot = 1, iimag = info.iroot[2];↵
                    for (int s = 0; s < (1 << (len - 2)); s++) {↵
                        mint irot2 = irot * irot;↵
                        mint irot3 = irot2 * irot;↵
                        int offset = s << (h - len + 2);↵
                        for (int i = 0; i < p; i++) {↵
                            auto a0 = 1ULL * a[i + offset + 0 * p].val();↵
                            auto a1 = 1ULL * a[i + offset + 1 * p].val();↵
                            auto a2 = 1ULL * a[i + offset + 2 * p].val();↵
                            auto a3 = 1ULL * a[i + offset + 3 * p].val();↵
 ↵
                            auto a2na3iimag =↵
                                1ULL *↵
                                mint((mint::mod() + a2 - a3) * iimag.val()).val();↵
 ↵
                            a[i + offset] = a0 + a1 + a2 + a3;↵
                            a[i + offset + 1 * p] =↵
                                (a0 + (mint::mod() - a1) + a2na3iimag) * irot.val();↵
                            a[i + offset + 2 * p] =↵
                                (a0 + a1 + (mint::mod() - a2) + (mint::mod() - a3)) *↵
                                irot2.val();↵
                            a[i + offset + 3 * p] =↵
                                (a0 + (mint::mod() - a1) + (mint::mod() - a2na3iimag)) *↵
                                irot3.val();↵
                        }↵
                        if (s + 1 != (1 << (len - 2)))↵
                            irot *= info.irate3[countr_zero(~(unsigned int)(s))];↵
                    }↵
                    len -= 2;↵
                }↵
            }↵
        }↵
 ↵
        template <class mint, internal::is_static_modint_t<mint>* = nullptr>↵
        std::vector<mint> convolution_naive(const std::vector<mint>& a,↵
            const std::vector<mint>& b) {↵
            int n = int(a.size()), m = int(b.size());↵
            std::vector<mint> ans(n + m - 1);↵
            if (n < m) {↵
                for (int j = 0; j < m; j++) {↵
                    for (int i = 0; i < n; i++) {↵
                        ans[i + j] += a[i] * b[j];↵
                    }↵
                }↵
            }↵
            else {↵
                for (int i = 0; i < n; i++) {↵
                    for (int j = 0; j < m; j++) {↵
                        ans[i + j] += a[i] * b[j];↵
                    }↵
                }↵
            }↵
            return ans;↵
        }↵
 ↵
        template <class mint, internal::is_static_modint_t<mint>* = nullptr>↵
        std::vector<mint> convolution_fft(std::vector<mint> a, std::vector<mint> b) {↵
            int n = int(a.size()), m = int(b.size());↵
            int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));↵
            a.resize(z);↵
            internal::butterfly(a);↵
            b.resize(z);↵
            internal::butterfly(b);↵
            for (int i = 0; i < z; i++) {↵
                a[i] *= b[i];↵
            }↵
            internal::butterfly_inv(a);↵
            a.resize(n + m - 1);↵
            mint iz = mint(z).inv();↵
            for (int i = 0; i < n + m - 1; i++) a[i] *= iz;↵
            return a;↵
        }↵
 ↵
    }  // namespace internal↵
 ↵
    template <class mint, internal::is_static_modint_t<mint>* = nullptr>↵
    std::vector<mint> convolution(std::vector<mint>&& a, std::vector<mint>&& b) {↵
        int n = int(a.size()), m = int(b.size());↵
        if (!n || !m) return {};↵
 ↵
        int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));↵
        assert((mint::mod() - 1) % z == 0);↵
 ↵
        if (std::min(n, m) <= 60) return convolution_naive(a, b);↵
        return internal::convolution_fft(a, b);↵
    }↵
    template <class mint, internal::is_static_modint_t<mint>* = nullptr>↵
    std::vector<mint> convolution(const std::vector<mint>& a,↵
        const std::vector<mint>& b) {↵
        int n = int(a.size()), m = int(b.size());↵
        if (!n || !m) return {};↵
 ↵
        int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));↵
        assert((mint::mod() - 1) % z == 0);↵
 ↵
        if (std::min(n, m) <= 60) return convolution_naive(a, b);↵
        return internal::convolution_fft(a, b);↵
    }↵
 ↵
    template <unsigned int mod = 998244353,↵
        class T,↵
        std::enable_if_t<internal::is_integral<T>::value>* = nullptr>↵
    std::vector<T> convolution(const std::vector<T>& a, const std::vector<T>& b) {↵
        int n = int(a.size()), m = int(b.size());↵
        if (!n || !m) return {};↵
 ↵
        using mint = static_modint<mod>;↵
 ↵
        int z = (int)internal::bit_ceil((unsigned int)(n + m - 1));↵
        assert((mint::mod() - 1) % z == 0);↵
 ↵
        std::vector<mint> a2(n), b2(m);↵
        for (int i = 0; i < n; i++) {↵
            a2[i] = mint(a[i]);↵
        }↵
        for (int i = 0; i < m; i++) {↵
            b2[i] = mint(b[i]);↵
        }↵
        auto c2 = convolution(std::move(a2), std::move(b2));↵
        std::vector<T> c(n + m - 1);↵
        for (int i = 0; i < n + m - 1; i++) {↵
            c[i] = c2[i].val();↵
        }↵
        return c;↵
    }↵
 ↵
    std::vector<long long> convolution_ll(const std::vector<long long>& a,↵
        const std::vector<long long>& b) {↵
        int n = int(a.size()), m = int(b.size());↵
        if (!n || !m) return {};↵
 ↵
        static constexpr unsigned long long MOD1 = 754974721;  // 2^24↵
        static constexpr unsigned long long MOD2 = 167772161;  // 2^25↵
        static constexpr unsigned long long MOD3 = 469762049;  // 2^26↵
        static constexpr unsigned long long M2M3 = MOD2 * MOD3;↵
        static constexpr unsigned long long M1M3 = MOD1 * MOD3;↵
        static constexpr unsigned long long M1M2 = MOD1 * MOD2;↵
        static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;↵
 ↵
        static constexpr unsigned long long i1 =↵
            internal::inv_gcd(MOD2 * MOD3, MOD1).second;↵
        static constexpr unsigned long long i2 =↵
            internal::inv_gcd(MOD1 * MOD3, MOD2).second;↵
        static constexpr unsigned long long i3 =↵
            internal::inv_gcd(MOD1 * MOD2, MOD3).second;↵
 ↵
        static constexpr int MAX_AB_BIT = 24;↵
        static_assert(MOD1 % (1ull << MAX_AB_BIT) == 1, "MOD1 isn't enough to support an array length of 2^24.");↵
        static_assert(MOD2 % (1ull << MAX_AB_BIT) == 1, "MOD2 isn't enough to support an array length of 2^24.");↵
        static_assert(MOD3 % (1ull << MAX_AB_BIT) == 1, "MOD3 isn't enough to support an array length of 2^24.");↵
        assert(n + m - 1 <= (1 << MAX_AB_BIT));↵
 ↵
        auto c1 = convolution<MOD1>(a, b);↵
        auto c2 = convolution<MOD2>(a, b);↵
        auto c3 = convolution<MOD3>(a, b);↵
 ↵
        std::vector<long long> c(n + m - 1);↵
        for (int i = 0; i < n + m - 1; i++) {↵
            unsigned long long x = 0;↵
            x += (c1[i] * i1) % MOD1 * M2M3;↵
            x += (c2[i] * i2) % MOD2 * M1M3;↵
            x += (c3[i] * i3) % MOD3 * M1M2;↵
            // B = 2^63, -B <= x, r(real value) < B↵
            // (x, x - M, x - 2M, or x - 3M) = r (mod 2B)↵
            // r = c1[i] (mod MOD1)↵
            // focus on MOD1↵
            // r = x, x - M', x - 2M', x - 3M' (M' = M % 2^64) (mod 2B)↵
            // r = x,↵
            //     x - M' + (0 or 2B),↵
            //     x - 2M' + (0, 2B or 4B),↵
            //     x - 3M' + (0, 2B, 4B or 6B) (without mod!)↵
            // (r - x) = 0, (0)↵
            //           - M' + (0 or 2B), (1)↵
            //           -2M' + (0 or 2B or 4B), (2)↵
            //           -3M' + (0 or 2B or 4B or 6B) (3) (mod MOD1)↵
            // we checked that↵
            //   ((1) mod MOD1) mod 5 = 2↵
            //   ((2) mod MOD1) mod 5 = 3↵
            //   ((3) mod MOD1) mod 5 = 4↵
            long long diff =↵
                c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1));↵
            if (diff < 0) diff += MOD1;↵
            static constexpr unsigned long long offset[5] = {↵
                0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3 };↵
            x -= offset[diff % 5];↵
            c[i] = x;↵
        }↵
 ↵
        return c;↵
    }↵
 ↵
}  // namespace atcoder↵
void Init(int t) {↵
 ↵
}↵
#define MOD 998244353↵
namespace sha256 {↵
    using u8 = uint8_t;↵
    using u32 = uint32_t;↵
    using u64 = uint64_t;↵
 ↵
    static const u32 K[64] = {↵
        0x428a2f98u, 0x71374491u, 0xb5c0fbcfu, 0xe9b5dba5u, 0x3956c25bu, 0x59f111f1u, 0x923f82a4u, 0xab1c5ed5u,↵
        0xd807aa98u, 0x12835b01u, 0x243185beu, 0x550c7dc3u, 0x72be5d74u, 0x80deb1feu, 0x9bdc06a7u, 0xc19bf174u,↵
        0xe49b69c1u, 0xefbe4786u, 0x0fc19dc6u, 0x240ca1ccu, 0x2de92c6fu, 0x4a7484aau, 0x5cb0a9dcu, 0x76f988dau,↵
        0x983e5152u, 0xa831c66du, 0xb00327c8u, 0xbf597fc7u, 0xc6e00bf3u, 0xd5a79147u, 0x06ca6351u, 0x14292967u,↵
        0x27b70a85u, 0x2e1b2138u, 0x4d2c6dfcu, 0x53380d13u, 0x650a7354u, 0x766a0abbu, 0x81c2c92eu, 0x92722c85u,↵
        0xa2bfe8a1u, 0xa81a664bu, 0xc24b8b70u, 0xc76c51a3u, 0xd192e819u, 0xd6990624u, 0xf40e3585u, 0x106aa070u,↵
        0x19a4c116u, 0x1e376c08u, 0x2748774cu, 0x34b0bcb5u, 0x391c0cb3u, 0x4ed8aa4au, 0x5b9cca4fu, 0x682e6ff3u,↵
        0x748f82eeu, 0x78a5636fu, 0x84c87814u, 0x8cc70208u, 0x90befffau, 0xa4506cebu, 0xbef9a3f7u, 0xc67178f2u↵
    };↵
 ↵
    inline u32 rotr(u32 x, int r) { return (x >> r) | (x << (32 - r)); }↵
 ↵
    struct Sha256 {↵
        u32 h[8];↵
        u64 total;↵
        u8 buf[64];↵
        size_t blen;↵
 ↵
        void init() {↵
            static const u32 iv[8] = { 0x6a09e667u, 0xbb67ae85u, 0x3c6ef372u, 0xa54ff53au,↵
                                       0x510e527fu, 0x9b05688cu, 0x1f83d9abu, 0x5be0cd19u };↵
            for (int i = 0; i < 8; i++) h[i] = iv[i];↵
            total = 0;↵
            blen = 0;↵
        }↵
 ↵
        void compress(const u8* p) {↵
            u32 w[64];↵
            for (int i = 0; i < 16; i++)↵
                w[i] = (u32)p[4 * i] << 24 | (u32)p[4 * i + 1] << 16 | (u32)p[4 * i + 2] << 8 | (u32)p[4 * i + 3];↵
            for (int i = 16; i < 64; i++) {↵
                u32 s0 = rotr(w[i - 15], 7) ^ rotr(w[i - 15], 18) ^ (w[i - 15] >> 3);↵
                u32 s1 = rotr(w[i - 2], 17) ^ rotr(w[i - 2], 19) ^ (w[i - 2] >> 10);↵
                w[i] = w[i - 16] + s0 + w[i - 7] + s1;↵
            }↵
            u32 a = h[0], b = h[1], c = h[2], d = h[3], e = h[4], f = h[5], g = h[6], hh = h[7];↵
            for (int i = 0; i < 64; i++) {↵
                u32 t1 = hh + (rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25)) + ((e & f) ^ (~e & g)) + K[i] + w[i];↵
                u32 t2 = (rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22)) + ((a & b) ^ (a & c) ^ (b & c));↵
                hh = g; g = f; f = e; e = d + t1; d = c; c = b; b = a; a = t1 + t2;↵
            }↵
            h[0] += a; h[1] += b; h[2] += c; h[3] += d;↵
            h[4] += e; h[5] += f; h[6] += g; h[7] += hh;↵
        }↵
 ↵
        void update(const void* data, size_t n) {↵
            const u8* p = (const u8*)data;↵
            total += n;↵
            while (n) {↵
                size_t take = 64 - blen;↵
                if (take > n) take = n;↵
                memcpy(buf + blen, p, take);↵
                blen += take; p += take; n -= take;↵
                if (blen == 64) { compress(buf); blen = 0; }↵
            }↵
        }↵
 ↵
        void finish(u8 out[32]) {↵
            u64 bits = total << 3;↵
            u8 pad[72];↵
            size_t np = 0;↵
            pad[np++] = 0x80;↵
            while ((blen + np) % 64 != 56) pad[np++] = 0;↵
            for (int i = 0; i < 8; i++) pad[np++] = (u8)(bits >> (56 - 8 * i));↵
            for (size_t i = 0; i < np; i++) {↵
                buf[blen++] = pad[i];↵
                if (blen == 64) { compress(buf); blen = 0; }↵
            }↵
            for (int i = 0; i < 8; i++) {↵
                out[4 * i] = (u8)(h[i] >> 24);↵
                out[4 * i + 1] = (u8)(h[i] >> 16);↵
                out[4 * i + 2] = (u8)(h[i] >> 8);↵
                out[4 * i + 3] = (u8)h[i];↵
            }↵
        }↵
    };↵
 ↵
    inline void sha256(const void* data, size_t n, u8 out[32]) {↵
        Sha256 c;↵
        c.init();↵
        c.update(data, n);↵
        c.finish(out);↵
    }↵
}↵
struct WeightStream {↵
    uint8_t seed[32];↵
    uint64_t pool[4];↵
    uint64_t counter;↵
    int left;↵
 ↵
    WeightStream(const uint8_t s[32]) {↵
        memcpy(seed, s, 32);↵
        counter = 0;↵
        left = 0;↵
    }↵
 ↵
    uint64_t next64() {↵
        if (!left) {↵
            uint8_t in[40], out[32];↵
            memcpy(in, seed, 32);↵
            for (int i = 0; i < 8; i++) in[32 + i] = (uint8_t)(counter >> (8 * i));↵
            sha256::sha256(in, 40, out);↵
            memcpy(pool, out, 32);↵
            left = 4;↵
            ++counter;↵
        }↵
        return pool[--left];↵
    }↵
 ↵
    // non-zero weight; the 64-bit modulo bias is about 1e-10↵
    uint32_t nextWeight() {↵
        uint64_t x;↵
        do {↵
            x = next64() % (uint64_t)MOD;↵
        } while (x == 0);↵
        return (uint32_t)x;↵
    }↵
};↵
using mi = atcoder::modint998244353;↵
void Solve() {↵
    int n;↵
    string s;↵
    cin >> n >> s;↵
    vector<int>a(n);↵
    cin >> a;↵
    for (auto& u : a)u--;↵
    int tmp = 1 << 20, res = 0;↵
    vector<mi>g(n);↵
    for (int i = 0; i < n; i++)g[i] = s[i] - 'a';↵
    reverse(all(g));↵
    auto h = sha256::Sha256();↵
    h.init();↵
    h.update(s.data(), n);↵
    h.update(a.data(), n * sizeof(int));↵
    h.update("LNight", 7);↵
    h.update(&n, sizeof(int));↵
    uint8_t sha[32];↵
    h.finish(sha);↵
    WeightStream ws(sha);↵
 ↵
    vector<vector<mi>>list(4, vector<mi>(n));↵
 ↵
    for (auto& u : list) {↵
        for (auto& z : u)z = ws.nextWeight();↵
    }↵
 ↵
    auto ck = [&](int x)->bool {↵
        if (x > n)return 0;↵
        vector<mi>d(n);↵
        vector<pair<ull, ull>>z(n);↵
        for (int k = 0; k < 4; k++) {↵
            for (int i = 0; i < x; i++)d[a[i]] = list[k][i];↵
            auto tmp = convolution(g, d);↵
            vector<mi>r(n);↵
            for (int i = 0; i < tmp.size(); i++) {↵
                r[(n - 1 - i + n) % n] += tmp[i];↵
            }↵
            for (int i = 0; i < n; i++) {↵
                if (k == 0)z[i].first = r[i].val();↵
                else if (k == 1)z[i].first = (z[i].first << 32) | r[i].val();↵
                else if (k == 2)z[i].second = r[i].val();↵
                else if (k == 3)z[i].second = (z[i].second << 32) | r[i].val();↵
            }↵
        }↵
        vector<int>pt(n);↵
        for (int i = 0; i < n; i++)pt[i] = i;↵
        sort(all(pt), [&](auto x, auto y) {return z[x] < z[y]; });↵
        for (int l = 0; l < n;) {↵
            int r = l + 1;↵
            while (r < n && z[pt[r]] == z[pt[l]])r++;↵
            for (int i = l; i < r; i++) {↵
                for (int j = i + 1; j < r; j++) {↵
                    bool flag = 1;↵
                    for (int k = 0; k < x; k++) {↵
                        if (s[(a[k] + pt[i]) % n] != s[(a[k] + pt[j]) % n]) {↵
                            flag = 0;↵
                            break;↵
                        }↵
                    }↵
                    if (flag)return 1;↵
                }↵
            }↵
            l = r;↵
        }↵
        return 0;↵
        };↵
    while (tmp)↵
    {↵
        if (ck(res + tmp))res += tmp;↵
        tmp >>= 1;↵
    }↵
    cout << res << endl;↵
}↵
signed main()↵
{↵
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
    cout << fixed << setprecision(18);↵
    int T = 1;↵
    cin >> T;↵
    int tit = clock();↵
    Init(T);↵
    while (T--)  Solve();↵
    cerr << clock() - tit << endl;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### [problem:2287E1]↵
↵
My initial problem only had an $n \le 10^5$ version and an $n \le 500$ version; thanks to [user:Error_Yuan,2026-11-21] for proposing this $n \le 10^4$ version.↵
↵
<spoiler summary="Hint 1">↵
If the two maxima differ, or if they are equal with different multiplicities, the position is already trivial: keep attacking the opponent's maximum, and the outcome is decided by whose maximum is larger and, on a tie, by who owns more copies of it.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
A player has only two useful attack targets: the opponent's maximum value and the opponent's strict second maximum. Attacking anything smaller brings no extra profit.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Both players may play optimally without ever skipping a turn: skipping never turns a lost position into a non-lost one, so every move may be assumed to be a real attack.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2287E1]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
//I must have missed the evolution memo.↵
//In case I never coding, good afternoon, good evening, and good night.↵
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING↵
#define _SILENCE_CXX20_CISO646_REMOVED_WARNING↵
#define _CRT_SECURE_NO_WARNINGS↵
#pragma warning(disable : 4700)↵
#include "bits/stdc++.h"↵
#include <array>↵
#if 0↵
#include "atcoder/all"↵
using namespace atcoder;↵
#endif↵
using namespace std;↵
template<typename T1, typename T2> istream& operator>>(istream& cin, pair<T1, T2>& a) { return cin >> a.first >> a.second; }↵
template<typename T1> istream& operator>>(istream& cin, vector<T1>& a) { for (auto& x : a) cin >> x; return cin; }↵
template<typename T1> istream& operator>>(istream& cin, valarray<T1>& a) { for (auto& x : a) cin >> x; return cin; }↵
template<typename T1, typename T2> ostream& operator<<(ostream& cout, const pair<T1, T2>& a) { return cout << a.first << ' ' << a.second; }↵
template<typename T1, typename T2> ostream& operator<<(ostream& cout, const vector<pair<T1, T2>>& a) { for (auto& x : a) cout << x << '\n'; return cout; }↵
template<typename T1> ostream& operator<<(ostream& cout, const vector<T1>& a) { int n = a.size(); if (!n) return cout; cout << a[0]; for (int i = 1; i < n; i++) cout << ' ' << a[i]; return cout; }↵
template<typename T1, typename T2> bool cmin(T1& x, const T2& y) { if (y < x) { x = y; return 1; } return 0; }↵
template<typename T1, typename T2> bool cmax(T1& x, const T2& y) { if (x < y) { x = y; return 1; } return 0; }↵
template<typename T1> vector<T1> range(T1 l, T1 r, T1 step = 1) { assert(step > 0); int n = (r - l + step - 1) / step, i; vector<T1> res(n); for (i = 0; i < n; i++) res[i] = l + step * i; return res; }↵
template<typename T1> basic_string<T1> operator*(const basic_string<T1>& s, int m) { auto r = s; m *= s.size(); r.resize(m); for (int i = s.size(); i < m; i++) r[i] = r[i - s.size()]; return r; }↵
#if !defined(ONLINE_JUDGE)&&defined(LOCAL)↵
#include "my_header\debug.h"↵
#else↵
#define dbg(...) ;↵
#define dbgn(...) ;↵
#endif↵
typedef unsigned int ui;↵
typedef double db;↵
typedef long long ll;↵
typedef unsigned long long ull;↵
#define all(x) (x).begin(),(x).end()↵
#define Endl endl↵
#define THREADCNT 8↵
#define MY_NAME "LNight"↵
#define NAN 0.1217728619↵
#define small_queue(name, ...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>name↵
#define small_queue_type(...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>↵
#define MOD 998244353↵
void Init(int t) {↵
 ↵
}↵
pair<bool, bool> check(const vector<int>& a, const vector<int>& b) {↵
    int n = a.size(), m = b.size();↵
    int lim = max(n, m), inf = n + 1;↵
    vector<int> f(lim + 1), g(lim + 1);↵
    vector<int> nf(lim + 1), ng(lim + 1);↵
 ↵
    f[0] = g[0] = 1;↵
    for (int r = 1; r <= lim; ++r) {↵
        f[r] = g[r - 1];↵
        g[r] = max(f[r] + 1, f[r - 1]);↵
    }↵
 ↵
    int i = 0;↵
 ↵
    for (int l = 0; l < m; ) {↵
        int r = l;↵
        while (r < m && b[r] == b[l]) ++r;↵
        while (i < n && a[i] < b[l]) ++i;↵
        int p = i;↵
        while (p < n && a[p] == b[l]) ++p;↵
        int ca = p - i;↵
        int cb = r - l;↵
        vector<int> base_f(cb + 1), base_g(cb + 1);↵
        for (int s = 1; s <= cb; ++s) {↵
            int v;↵
 ↵
            if (s < ca) v = i + s + 1;↵
            else if (p < n) v = p + 1;↵
            else v = inf;↵
            base_f[s] = base_g[s] = v;↵
 ↵
            if (s <= ca) {↵
                if (i >= f[s]) base_f[s] = min(base_f[s], i + s);↵
                if (i >= g[s]) base_g[s] = min(base_g[s], i + s);↵
            }↵
        }↵
 ↵
        for (int s = 1; s <= cb; ++s) {↵
            nf[0] = base_f[s];↵
            ng[0] = base_g[s];↵
            for (int k = 1; k <= lim; ++k) {↵
                nf[k] = min(g[k], ng[k - 1]);↵
                ng[k] = max(nf[k] + 1, nf[k - 1]);↵
            }↵
            f.swap(nf);↵
            g.swap(ng);↵
        }↵
        l = r;↵
    }↵
    return { n >= f[0], n >= g[0] };↵
}↵
 ↵
int solve(vector<int> a, vector<int> b) {↵
    pair<int, int> alice = check(a, b);↵
    if (alice.first) return 1;↵
    pair<int, int> bob = check(b, a);↵
    if (bob.second) return -1;↵
    return 0;↵
}↵
void Solve() {↵
    int n, m;↵
    cin >> n >> m;↵
    vector<int>a(n), b(m);↵
    cin >> a >> b;↵
    sort(all(a));↵
    sort(all(b));↵
    int res = solve(a, b);↵
    if (res == 1)cout << "A" << endl;↵
    else if (res == -1)cout << "B" << endl;↵
    else cout << "C" << endl;↵
}↵
signed main()↵
{↵
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
    cout << fixed << setprecision(18);↵
    int T = 1;↵
    cin >> T;↵
    int tit = clock();↵
    Init(T);↵
    while (T--)  Solve();↵
    cerr << clock() - tit << endl;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
The idea comes from the power level settings of some fantasy works. In many fantasy works every character has a power level, and the levels differ wildly (for example, Tier 10 is an ordinary human, while Tier 9 is a superhuman). In this setting I created this problem, so that you can see how a battle between two groups should happen in such a fantasy world, and what the best arrangement is if a group wants to defeat another group.↵
↵
### [problem:2287E2]↵
↵
Codex did not pass this problem during testing, which surprised me a lot.↵
↵
Before reading, please go through the hints of [problem:2287E1], but no need read its tutorial, because what follows is completely different.↵
↵
<spoiler summary="Hint 1">↵
Sort the input. You can see that at any moment both players hold a prefix plus $k$ copies of the maximum value. This is already an $O(n^3)$-level DP.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
We focus on the case $k = 0$: at this moment both players hold only a prefix, and we enter a subproblem.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Recall Hint 1 of the easy version: only $O(n)$ subproblems are not trivial.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Every state with $k > 0$ can be derived from the states with $k = 0$, and we only need to find the derivation rule.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2287E2]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
//I must have missed the evolution memo.↵
//In case I never coding, good afternoon, good evening, and good night.↵
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING↵
#define _SILENCE_CXX20_CISO646_REMOVED_WARNING↵
#define _CRT_SECURE_NO_WARNINGS↵
#pragma warning(disable : 4700)↵
#include "bits/stdc++.h"↵
#if 0↵
#include "atcoder/all"↵
using namespace atcoder;↵
#endif↵
using namespace std;↵
template<typename T1, typename T2> istream& operator>>(istream& cin, pair<T1, T2>& a) { return cin >> a.first >> a.second; }↵
template<typename T1> istream& operator>>(istream& cin, vector<T1>& a) { for (auto& x : a) cin >> x; return cin; }↵
template<typename T1> istream& operator>>(istream& cin, valarray<T1>& a) { for (auto& x : a) cin >> x; return cin; }↵
template<typename T1, typename T2> ostream& operator<<(ostream& cout, const pair<T1, T2>& a) { return cout << a.first << ' ' << a.second; }↵
template<typename T1, typename T2> ostream& operator<<(ostream& cout, const vector<pair<T1, T2>>& a) { for (auto& x : a) cout << x << '\n'; return cout; }↵
template<typename T1> ostream& operator<<(ostream& cout, const vector<T1>& a) { int n = a.size(); if (!n) return cout; cout << a[0]; for (int i = 1; i < n; i++) cout << ' ' << a[i]; return cout; }↵
template<typename T1, typename T2> bool cmin(T1& x, const T2& y) { if (y < x) { x = y; return 1; } return 0; }↵
template<typename T1, typename T2> bool cmax(T1& x, const T2& y) { if (x < y) { x = y; return 1; } return 0; }↵
template<typename T1> vector<T1> range(T1 l, T1 r, T1 step = 1) { assert(step > 0); int n = (r - l + step - 1) / step, i; vector<T1> res(n); for (i = 0; i < n; i++) res[i] = l + step * i; return res; }↵
template<typename T1> basic_string<T1> operator*(const basic_string<T1>& s, int m) { auto r = s; m *= s.size(); r.resize(m); for (int i = s.size(); i < m; i++) r[i] = r[i - s.size()]; return r; }↵
#if !defined(ONLINE_JUDGE)&&defined(LOCAL)↵
#include "my_header\debug.h"↵
#else↵
#define dbg(...) ;↵
#define dbgn(...) ;↵
#endif↵
typedef unsigned int ui;↵
typedef double db;↵
typedef long long ll;↵
typedef unsigned long long ull;↵
#define all(x) (x).begin(),(x).end()↵
#define Endl endl↵
#define THREADCNT 8↵
#define MY_NAME "LNight"↵
#define NAN 0.1217728619↵
#define small_queue(name, ...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>name↵
#define small_queue_type(...) priority_queue<__VA_ARGS__, vector<__VA_ARGS__>, greater<__VA_ARGS__>>↵
void Init(int t) {↵
 ↵
}↵
struct fwt {↵
    int n;↵
    vector<int>d;↵
    fwt(int _n) {↵
        n = _n;↵
        d.resize(n + 1, -1);↵
    }↵
    void set(int x, int v) {↵
        while (x <= n) {↵
            d[x] = max(d[x], v);↵
            x += x & -x;↵
        }↵
    }↵
    int get(int x) {↵
        int res = -1;↵
        while (x) {↵
            res = max(res, d[x]);↵
            x -= x & -x;↵
        }↵
        return res;↵
    }↵
};↵
int sv(vector<int>a, vector<int>b) {↵
    int n = a.size();↵
    int m = b.size();↵
    vector<vector<int>>dpa(2, vector<int>(m + 1));//面对有i个的鲍勃,爱丽丝先手需要dpa[0][i]个才能赢,爱丽丝后手需要dpa[1][i]个才能赢↵
    vector<vector<int>>dpb(2, vector<int>(n + 1));//面对有i个的爱丽丝,鲍勃先手需要dpb[1][i]个才能赢,鲍勃后手需要dpb[0][i]个才能赢↵
    fwt sta(n + m + 10);//鲍勃行动时1的查询,pa-pb+m+1↵
    fwt stb(n + m + 10);//爱丽丝行动时-1的查询,pb-pa+n+1↵
    vector<vector<int>>draw(2, vector<int>(n + m + 10, -1));//平局状态,[[pb-pa+m+1]=pa,[pa-pb+m+1]=pb]↵
    draw[0][n + 1] = 0;↵
    draw[1][m + 1] = 0;↵
    sta.set(m + 2, 0);↵
    stb.set(n + 2, 0);↵
    int pa = 1, pb = 1;↵
    int z = 1;↵
    while (pa <= n && pb <= m) {↵
        if (a[pa - 1] != b[pb - 1]) {↵
            if (a[pa - 1] > b[pb - 1]) {↵
                dpa[0][pb] = dpa[1][pb] = pa;//役满确定↵
                sta.set(dpa[1][pb] - pb + m + 1, pb);↵
                pb++;↵
                continue;↵
            }↵
            else {↵
                dpb[0][pa] = dpb[1][pa] = pb;//役满确定↵
                stb.set(dpb[0][pa] - pa + n + 1, pa);↵
                pa++;↵
                continue;↵
            }↵
        }↵
        if (pa > 1 && a[pa - 2] == a[pa - 1])z++;↵
        else z = 1;↵
        int x = pa - z;↵
        int y = pb - z;↵
        //役满机会↵
        dpa[0][pb] = dpa[1][pb] = pa + 1;↵
        dpb[0][pa] = dpb[1][pa] = pb + 1;↵
 ↵
        {//Alice first↵
            int aw, ad, bw, bd;//分别代表F上的1,F上的0,G上的-1,G上的0↵
            int tmp = 0;↵
            aw = y - sta.get(x - z + 1 - y + m + 1);↵
            bw = x - stb.get(y - z - x + n + 1);↵
            ad = y - draw[1][x - z + 1 - y + m + 1];↵
            bd = x - draw[0][y - z - x + n + 1];↵
            if (aw != y + 1 && (bw == x + 1 || aw <= bw)) {//aw <= bw + z + 1 会错误的让爱丽丝赢,aw<=bw - 1 - z会错误的让alice不赢↵
                if (bd == x + 1 || bd >= aw)tmp = 1;//bd + z + 3>=aw 会错误的让爱丽丝赢,aw<=bd - z - 1会错误的让alice不赢↵
            }↵
            else if (bw != x + 1 && (aw == y + 1 || aw > bw)) {//aw + z + 1 > bw会错误的让鲍勃赢,aw - z - 1 > bw 会错误的让鲍勃不赢。↵
                if (ad == y + 1 || ad > bw)tmp = -1;//ad + z + 3 > bw会错误的让鲍勃赢,ad - z - 1 > bw 会错误的让鲍勃不赢。↵
            }↵
            if (tmp == 1) {↵
                dpa[0][pb] = pa;↵
            }↵
            else if (tmp == -1) {↵
                dpb[0][pa] = pb;↵
            }↵
            else {↵
                draw[0][pb - pa + n + 1] = pa;↵
            }↵
        }↵
        {//Bob first↵
            int aw, ad, bw, bd;↵
            int tmp = 0;↵
            aw = y - sta.get(x - z - y + m + 1);↵
            bw = x - stb.get(y + 1 - z - x + n + 1);↵
            ad = y - draw[1][x - z - y + m + 1];↵
            bd = x - draw[0][y + 1 - z - x + n + 1];↵
            if (aw != y + 1 && (bw == x + 1 || aw < bw)) {//aw < bw + z + 1 会错误的让爱丽丝赢,aw<bw - 1 - z会错误的让alice不赢↵
                if (bd == x + 1 || bd > aw)tmp = 1;//bd + z + 3>aw 会错误的让爱丽丝赢,aw<bd - z - 1会错误的让alice不赢↵
            }↵
            else if (bw != x + 1 && (aw == y + 1 || aw >= bw)) {//aw + z + 1 >= bw会错误的让鲍勃赢,aw - z - 1 >= bw 会错误的让鲍勃不赢。↵
                if (ad == y + 1 || ad >= bw)tmp = -1;//ad + z + 3 >= bw会错误的让鲍勃赢,ad - z - 1 >= bw 会错误的让鲍勃不赢。↵
            }↵
            if (tmp == 1) {↵
                dpa[1][pb] = pa;↵
            }↵
            else if (tmp == -1) {↵
                dpb[1][pa] = pb;↵
            }↵
            else {↵
                draw[1][pa - pb + m + 1] = pb;↵
            }↵
        }↵
 ↵
        sta.set(dpa[1][pb] - pb + m + 1, pb);↵
        stb.set(dpb[0][pa] - pa + n + 1, pa);↵
        pa++;↵
        pb++;↵
    }↵
    int res = 0;↵
    if (pa > n) {↵
        if (dpb[0][n] <= m)res = -1;↵
        else if (draw[0][m + 1] == n)res = 0;↵
        else res = 1;↵
    }↵
    else {↵
        if (dpa[0][m] <= n)res = 1;↵
        else if (draw[0][m + 1] == n)res = 0;↵
        else res = -1;↵
    }↵
    return res;↵
}↵
void Solve() {↵
    int n, m;↵
    cin >> n >> m;↵
    vector<int>a(n), b(m);↵
    cin >> a >> b;↵
    sort(all(a));↵
    sort(all(b));↵
    int res = sv(a, b);↵
    if (res == 1)cout << "A" << endl;↵
    else if (res == -1)cout << "B" << endl;↵
    else cout << "C" << endl;↵
}↵
signed main()↵
{↵
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
    cout << fixed << setprecision(18);↵
    int T = 1;↵
    cin >> T;↵
    int tit = clock();↵
    Init(T);↵
    while (T--)  Solve();↵
    cerr << clock() - tit << endl;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
This problem was originally conceived as a two-attribute version (attack power and defense power), but I only know an $O(2^n)$ solution for it.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский LNight121 2026-11-21 21:06:13 78255
en3 Английский LNight121 2026-11-21 20:36:42 86
en2 Английский LNight121 2026-11-21 20:00:56 42 (published)
en1 Английский LNight121 2026-11-21 19:35:56 7560 Initial revision (saved to drafts)