这题能做到

$$ \boxed{O(m+n\log^2 n)} $$

时间，空间复杂度为 (O(m+n))。关键是先把最优策略的期望化成一组乘积，再用“分治 + 连续点插值 + NTT”消掉二次枚举。

完整 C++17 源码

1. 先确定最优策略

按照题面的操作顺序，一张牌在第 (t) 回合打出后，会在第 (t+n) 回合结束时回到手中，因此下次最早能在第 (t+n+1) 回合打出。

最优策略是：

• 当前任务的牌在手中，就立即打出。
• 否则，打出手中下一次被任务需要的位置最靠后的牌；不再需要的牌视为位置无穷远。

为什么第二步不会造成额外等待？

设当前等待任务 (i)。手中有 (n) 张不同的牌，而且都不是 (a_i)，因此选出的牌下一次需要的位置至少是 (i+n)。当前回合不能完成任务 (i)，所以这张牌下一次被需要时，最早已经是 (n+1) 回合之后，此时它已经回到手中。

这个策略只需要知道手牌和任务序列，不需要知道隐藏牌堆，符合题目的纯策略要求。

定义一张牌的初始等待量：

$$ r_x= \begin{cases} 0,&x\text{ 在初始手牌中},\\ p,&x\text{ 位于初始牌堆的第 }p\text{ 个位置}. \end{cases} $$

对于固定的初始洗牌，设 (T_i) 是完成任务 (i) 的最早回合，(T_0=0)，则

$$ T_i= \begin{cases} \max(T_{i-1}+1,\ r_{a_i}+1), & a_i\text{ 首次出现},\\[2mm] \max(T_{i-1}+1,\ T_{\operatorname{prev}_i}+n+1), & a_i\text{ 之前出现过}. \end{cases} $$

这些都是任何策略必须满足的下界，而上述策略恰好达到它们，所以这个递推给出的就是最优完成时间。

2. 将答案变成“带权初始位置的最大值”

设 (\operatorname{next}_i) 为 (a_i) 下一次出现的位置。从后往前计算：

$$ b_{m+1}=0, $$

$$ b_i= \max\left( b_{i+1}+1,\ b_{\operatorname{next}_i}+n+1 \right), $$

不存在下一次出现时，忽略第二项。

展开上一节的递推，可以得到

$$ \boxed{ T_m= \max_{x\text{ 在任务中出现}} \left(r_x+b_{\operatorname{first}(x)}\right). } $$

令

$$ B=b_1. $$

由于 (b_i\ge b_{i+1}+1)，所以 (b_i) 严格递减。

如果某个位置满足 (B-b_i\ge n)，那么

$$ r_{a_i}+b_i\le n+b_i\le B, $$

它的初始位置就不可能把答案推高到 (B) 以上。因此，我们只需要保留满足

$$ B-b_i

的前缀。

这个前缀中的牌一定互不相同。 因为如果 (a_p=a_i)、(p<i)，那么

$$ b_p\ge b_i+n+1 \quad\Longrightarrow\quad B-b_i\ge n+1. $$

设保留下来 (k) 个位置，并记

$$ c_j=B-b_{j+1}, \qquad 0\le j

于是

$$ 0=c_0

若用 (r_j) 表示牌 (a_{j+1}) 的初始等待量，则答案变成

$$ T_m=B+S, \qquad S=\max\left(0,\max_{0\le j

其中 (0\le S\le n)。到这里，所有与任务序列有关的处理只用了 (O(m+n)) 时间。

3. 写出期望的乘积公式

定义

$$ F(t)=\Pr(S\le t), \qquad 0\le t

条件 (S\le t) 等价于每张相关牌都满足

$$ r_j\le t+c_j. $$

当 (t+c_j\ge n) 时，这个限制自动成立。

对于其余的牌，允许的初始位置有：

$$ n+t+c_j $$

个，即 (n) 个初始手牌位置，加上牌堆前 (t+c_j) 个位置。

按照 (c_j) 从小到大放置这些牌。允许位置集合是嵌套的，所以处理第 (j) 张牌时，之前的 (j) 张牌都占用了它的允许位置。因此

$$ \boxed{ F(t)= \prod_{\substack{0\le j

由非负整数随机变量的尾和公式：

$$ \boxed{ \mathbb E[T_m] = B+n-\sum_{t=0}^{n-1}F(t). } $$

直接计算这里的所有乘积，就是 (O(n^2+m))。接下来优化这一部分。

4. 把二重乘积改成分治求值

对每个 (c_j)，令

$$ u=n-1-c_j. $$

因为所有 (c_j) 互不相同，所以每个 (u) 至多对应一个 (j)。

定义一次多项式

$$ L_u(X) = \frac{n+X+c_j-j}{2n-j} = 1+\frac{X-u-1}{2n-j}. $$

没有对应 (j) 的位置，令 (L_u(X)=1)。

原来的条件 (t+c_j<n) 恰好等价于 (t\le u)，因此

$$ \boxed{ F(t)=\prod_{u=t}^{n-1}L_u(t). } $$

我们现在要计算的是：

对每个 (t)，求后缀多项式乘积在 (X=t) 处的值。

分治时维护连续点上的值

对于区间 ([l,r])，定义

$$ P_{l,r}(X)=\prod_{u=l}^{r}L_u(X). $$

不维护系数，而是维护它在

$$ l,l+1,\ldots,r+1 $$

这些连续整数点上的值。

区间长度为 (s) 时，多项式次数不超过 (s)，所以这 (s+1) 个值足以确定它。

将区间分成左右两部分。合并时，对于左半部分的每个 (t)，补乘右半部分的全部因子：

$$ F(t)\gets F(t)\cdot P_{\mathrm{right}}(t). $$

同时，将左右多项式的取值都扩展到父区间需要的点，逐点相乘，就得到父区间的多项式取值。

连续点扩展只需要一次卷积

已知次数不超过 (s-1) 的多项式在

$$ 0,1,\ldots,s-1 $$

处的值 (f_0,\ldots,f_{s-1})，需要求后续连续点的值。

设

$$ A_i= \frac{(-1)^{s-1-i}f_i}{i!(s-1-i)!}, $$

$$ H_0=0,\qquad H_j=\frac1j\quad(j\ge1). $$

计算一次卷积

$$ C=A*H. $$

由拉格朗日插值，对 (k\ge s) 有

$$ \boxed{ f_k=\frac{k!}{(k-s)!}\,C_k. } $$

因此，向右扩展可以用一次 NTT 卷积完成。向左扩展则把原来的样本反转，向右扩展后再反转回来。

一个长度为 (s) 的分治节点，只需要两次规模为 (O(s)) 的卷积，时间为 (O(s\log s))。所以总复杂度为

$$ \boxed{ O(m+n\log^2 n) } $$

而不是使用普通多点求值后再额外多出一层对数。

5. 完整 C++17 实现

代码中的除法都通过模逆元实现，模数为题目要求的 (998244353)。

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
constexpr int MOD = 998244353;
constexpr int ROOT = 3;

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

void ntt(vector<int>& a, bool inverse) {
    int n = (int)a.size();

    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;
        while (j & bit) {
            j ^= bit;
            bit >>= 1;
        }
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        int step = mod_pow(ROOT, (MOD - 1) / len);
        if (inverse) step = mod_pow(step, MOD - 2);

        for (int l = 0; l < n; l += len) {
            int64 w = 1;
            for (int j = 0; j < len / 2; ++j) {
                int u = a[l + j];
                int v = int(w * a[l + j + len / 2] % MOD);

                int x = u + v;
                if (x >= MOD) x -= MOD;

                int y = u - v;
                if (y < 0) y += MOD;

                a[l + j] = x;
                a[l + j + len / 2] = y;
                w = w * step % MOD;
            }
        }
    }

    if (inverse) {
        int inv_n = mod_pow(n, MOD - 2);
        for (int& x : a)
            x = int((int64)x * inv_n % MOD);
    }
}

vector<int> convolution(vector<int> a, vector<int> b) {
    int need = (int)a.size() + (int)b.size() - 1;

    if (min(a.size(), b.size()) <= 32) {
        vector<int> c(need, 0);
        for (int i = 0; i < (int)a.size(); ++i)
            for (int j = 0; j < (int)b.size(); ++j)
                c[i + j] = int(
                    (c[i + j] + (int64)a[i] * b[j]) % MOD
                );
        return c;
    }

    int len = 1;
    while (len < need) len <<= 1;

    a.resize(len);
    b.resize(len);

    ntt(a, false);
    ntt(b, false);

    for (int i = 0; i < len; ++i)
        a[i] = int((int64)a[i] * b[i] % MOD);

    ntt(a, true);
    a.resize(need);
    return a;
}

struct Solver {
    int n;
    vector<int> inv, fac, ifac;
    vector<int> q, F;

    explicit Solver(int n_)
        : n(n_),
          inv(2 * n + 1),
          fac(2 * n + 1),
          ifac(2 * n + 1),
          q(n, 0),
          F(n) {

        inv[1] = 1;
        for (int i = 2; i <= 2 * n; ++i) {
            inv[i] = int(
                MOD - (int64)(MOD / i) * inv[MOD % i] % MOD
            );
        }

        fac[0] = ifac[0] = 1;
        for (int i = 1; i <= 2 * n; ++i) {
            fac[i] = int((int64)fac[i - 1] * i % MOD);
            ifac[i] = int((int64)ifac[i - 1] * inv[i] % MOD);
        }
    }

    // 已知次数不超过 s-1 的多项式在 0,...,s-1 的取值。
    // 用一次卷积补出 s,...,count-1 的取值。
    vector<int> extend_right(vector<int> f, int count) {
        int s = (int)f.size();
        if (s == count) return f;

        vector<int> a(s), b(count, 0);

        for (int i = 0; i < s; ++i) {
            a[i] = int(
                (int64)f[i] * ifac[i] % MOD
                * ifac[s - 1 - i] % MOD
            );

            if ((s - 1 - i) & 1)
                a[i] = (a[i] == 0 ? 0 : MOD - a[i]);
        }

        for (int i = 1; i < count; ++i)
            b[i] = inv[i];

        vector<int> c = convolution(move(a), move(b));

        f.resize(count);
        for (int i = s; i < count; ++i) {
            f[i] = int(
                (int64)c[i] * fac[i] % MOD
                * ifac[i - s] % MOD
            );
        }

        return f;
    }

    // 返回区间乘积多项式在 l,...,r+1 的取值。
    // 同时向 F[t] 中乘入当前区间内所有下标不小于 t 的因子。
    vector<int> divide(int l, int r) {
        if (l == r) {
            int x = 1 - q[l];
            if (x < 0) x += MOD;

            F[l] = x;
            return {x, 1};
        }

        int mid = (l + r) / 2;
        vector<int> left = divide(l, mid);
        vector<int> right = divide(mid + 1, r);

        int count = r - l + 2;

        left = extend_right(move(left), count);

        // 反转样本，把向左扩展转化为向右扩展。
        reverse(right.begin(), right.end());
        right = extend_right(move(right), count);
        reverse(right.begin(), right.end());

        for (int t = l; t <= mid; ++t)
            F[t] = int((int64)F[t] * right[t - l] % MOD);

        for (int i = 0; i < count; ++i)
            left[i] = int((int64)left[i] * right[i] % MOD);

        return left;
    }

    int solve(const vector<int>& a) {
        int m = (int)a.size();

        vector<int64> b(m + 1, 0);
        vector<int64> next_value(2 * n + 1, 0);

        for (int i = m - 1; i >= 0; --i) {
            b[i] = b[i + 1] + 1;

            if (next_value[a[i]] != 0)
                b[i] = max(b[i], next_value[a[i]] + n + 1);

            next_value[a[i]] = b[i];
        }

        int64 base = b[0];

        // 有贡献的任务构成一个前缀，且其中的牌互不相同。
        for (int i = 0; i < m && base - b[i] < n; ++i) {
            int c = int(base - b[i]);
            int u = n - 1 - c;
            q[u] = inv[2 * n - i];
        }

        divide(0, n - 1);

        int answer = int((base + n) % MOD);
        for (int x : F) {
            answer -= x;
            if (answer < 0) answer += MOD;
        }

        return answer;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n, m;
        cin >> n >> m;

        vector<int> a(m);
        for (int& x : a) cin >> x;

        Solver solver(n);
        cout << solver.solve(a) << '\n';
    }

    return 0;
}

这份实现已在本地对上题面的全部样例，并与直接计算乘积的二次算法做了 538 组对拍；另外对 60 组 (n=2,3) 的任务序列，枚举全部初始排列核对了期望。