设 $N=\max n$，模数为 $p=998244353$。下面给出时间复杂度 $O((N^2+T)\log^2(N+1))$、空间复杂度 $O(N^2+T)$ 的算法。 公开题解中的一种做法是按数值容斥，利用指数函数基底将预处理降到 $O(N^3)$，再以 $O(N)$ 回答一次询问；这里继续消去其中的状态，将计数归结为二元形式幂级数求逆，最后离线处理询问。
从容斥推到一个二元生成函数
记答案为 $A_{n,m}$，并补充定义 $A_{0,m}=1$、$A_{n,0}=[n=0]$。
首先，固定 $n$ 时，$A_{n,m}$ 是关于 $m$ 的至多 $n$ 次多项式。设 $c_{n,k}$ 表示恰好使用 $1,\ldots,k$ 中每个数的合法序列数。任意序列按照出现过的数的相对大小离散化，合法性不变，因此 $A_{n,m}=\sum_{k=0}^n c_{n,k}\binom{m}{k}$。这说明我们只需要求出 $0\le n,m\le N$ 的答案表，再用插值处理较大的 $m$，而不必真的沿着值域算到 $10^9$。
现在考虑如何快速生成这张表。
对于出现过的数值 $v$，记它第一次、最后一次出现的位置分别为 $L_v,R_v$。题目禁止的情况等价于存在一个 $v$，满足 $L_v < R_v$，且 $L_v$ 之前的数都小于 $v$，$R_v$ 之后的数都大于 $v$。必要性来自将原来的两个见证位置向第一次、最后一次出现的位置移动；充分性则直接取 $i=L_v,j=R_v$。
称这样的 $v$ 为一个“坏值”，对坏值集合容斥。也就是说，我们允许标记一些数值，要求被标记的数值确实是坏值，并赋予方案权重 $(-1)^{\text{标记数}}$。
从小到大插入数值。为了保证已经标记的数值仍然满足条件，需要维护一条分界线：分界线之前是锁定前缀，之后是自由后缀，未来更大的数只能插入自由后缀。 分界线恰好位于最后一个被标记数值的第一次出现之后；没有标记时，锁定前缀为空。
若当前插入数值 $b$ 不被标记，可以在自由后缀中任意插入若干个 $b$，包括零个。
若 $b$ 被标记，则先选择自由后缀的一个前缀，将其移入锁定前缀，再插入第一个 $b$，并将它也锁定。剩下的旧元素与若干个 $b$ 任意交错，最后再追加一个 $b$。这样第一个 $b$ 前面没有更大的数，最后一个 $b$ 后面没有更小的数，而且至少出现了两次。该转移还要乘上容斥系数 $-1$。
直接维护“处理了几个值、锁定长度、自由长度”仍然是三维状态。关键在于，自由后缀长度这一维，可以用 $j\mapsto c^j$ 作为基底处理。
用 $x$ 记录锁定前缀的长度，约定 $0^0=1$。最初只有自由长度为零的状态，其权重序列恰好是 $0^j$。假设当前某一项对自由长度 $j$ 的权重是 $c^j$，考虑插入下一个数值后的变化。
不标记新数值时，若新自由长度为 $j$，枚举其中有几个旧元素，由二项式定理得到 $\sum_{r=0}^j\binom jr c^r=(c+1)^j$。
标记新数值时，设先将 $s$ 个旧元素移入锁定前缀。锁定长度增加 $s+1$；新自由后缀最后一个位置被固定为新数值，因此对于 $j\ge1$，这一转移的贡献为 $-x^{s+1}c^s(c+1)^{j-1}$。对 $s$ 求和，得到 $-\frac{x}{1-cx}(c+1)^{j-1}$；而 $j=0$ 时贡献为零。
于是，两种情况合起来就是极其简单的基底转移：
$$ c^j\ \longmapsto\ \left(1-\frac{x}{(c+1)(1-cx)}\right)(c+1)^j +\frac{x}{(c+1)(1-cx)}\,0^j. $$
因此，基底下标每次只有两种变化：从 $c$ 增加到 $c+1$，或者重置为 $0$。
记 $\alpha_k(x)=1-\frac{x}{k(1-(k-1)x)}$，并令 $R_0(x)=1$、$R_k(x)=\prod_{i=1}^k\alpha_i(x)$。从下标 $0$ 出发，连续增加 $k$ 次的权重就是 $R_k$。如果连续增加 $k-1$ 次后重置，那么这个长度为 $k$ 的完整块权重为 $R_{k-1}(1-\alpha_k)=R_{k-1}-R_k$。
处理完所有数值时，还需要把自由后缀长度也计入序列总长度。因此，最终处在基底 $k^j$ 时，应乘上 $\sum_{j\ge0}k^jx^j=\frac1{1-kx}$。令 $Q_k(x)=\frac{R_k(x)}{1-kx}$，则一个长度为 $k$、结尾没有重置的尾块权重恰好是 $Q_k$。
整条转移路径唯一分解为若干个“以重置结束的完整块”，再接一个尾块。用 $y$ 记录处理过的数值个数，设 $Q(x,y)=\sum_{k\ge0}Q_k(x)y^k$，答案生成函数就等于尾块生成函数除以“$1-$完整块生成函数”。
进一步整理 $Q_k$ 的定义，有 $Q_0=1$，且 $Q_k(x)=\frac{k-(k^2-k+1)x}{k(1-kx)}Q_{k-1}(x)$。由此得到 $R_k-R_{k-1}=-\frac{x}{k}Q_{k-1}$，于是分母也可以直接用 $Q$ 表示。最终得到：
$$ F(x,y):=\sum_{n,m\ge0}A_{n,m}x^ny^m = \frac{Q(x,y)} {1-x\displaystyle\sum_{k\ge0}\frac{Q_k(x)}{k+1}y^{k+1}}. $$
原来的三维容斥，已经变成了一个二元形式幂级数的除法。
这些恒等式可以先在有理数域中理解。实际计算只保留 $0\le n,m\le N$，所涉及的整数除数均不超过 $N
近二次时间生成整张答案表
令 $q_{r,k}=[x^r]Q_k(x)$。由上面的相邻项递推，初值为 $q_{0,k}=1$、$q_{r,0}=0$（$r>0$），并且对于 $r,k\ge1$：
$$ q_{r,k} = kq_{r-1,k}+q_{r,k-1} -\left(k-1+\frac1k\right)q_{r-1,k-1}. $$
每个位置只依赖三个已经算出的值，所以全部 $0\le r,k\le N$ 的 $q_{r,k}$ 可以在 $O(N^2)$ 时间内求出。
记生成函数公式的分母为 $D(x,y)$。它的系数更简单：$d_{0,0}=1$，对于 $r,k\ge1$ 有 $d_{r,k}=-q_{r-1,k-1}/k$，其他边界位置为零。构造 $D$ 同样只需 $O(N^2)$ 时间。
接下来计算 $F=QD^{-1}\bmod(x^{N+1},y^{N+1})$。
注意到 $D(0,y)=1$，所以可以把系数环取为 $\mathbb F_p[y]/(y^{N+1})$，只对 $x$ 的精度进行倍增。从 $G=1$ 开始，若已有 $DG\equiv1\pmod{x^h}$，则更新 $G\leftarrow G(2-DG)\pmod{x^{2h},y^{N+1}}$。其正确性就是恒等式 $1-DG(2-DG)=(1-DG)^2$，与通常的一元多项式求逆完全相同。([arXiv][3])
这里需要说明二元乘法如何实现，否则容易把复杂度低估。
在 $x$ 方向长度为 $O(h)$、$y$ 方向长度为 $N+1$ 时，可以进行二维 NTT；也可以直接使用一元 NTT，将单项式 $x^iy^j$ 编码成 $z^{i(2N+1)+j}$。因为一次乘法中 $y$ 的次数最多为 $2N$，所以采用步长 $2N+1$ 不会发生维度之间的进位混淆。乘完后解码，再删除 $y$ 次数大于 $N$ 或 $x$ 次数超出当前精度的项。
步长不能直接取 $N+1$，也不能编码后直接做一次一元求逆。 前者会让 $y$ 方向溢出的项混入下一行；后者则没有在每一步执行所需的二元截断。编码只用于实现每一次二元乘法。
一次这样的乘法需要 $O(Nh\log(Nh))$ 时间。对 $h=1,2,4,\ldots$ 求和，整个求逆以及最后乘上 $Q$ 的时间为 $O(N^2\log(N+1))$，空间为 $O(N^2)$。
至此，所有 $0\le n,m\le N$ 的答案已经求出。预处理的主体不再有三次项。
将大量询问也降到多对数均摊代价
记 $P_n(z)$ 为满足 $P_n(m)=A_{n,m}$ 的答案多项式。前面已经证明 $\deg P_n\le n$，所以 $A_{n,0},\ldots,A_{n,n}$ 足以确定它。
不能对每一行用朴素方法展开拉格朗日插值，否则会重新引入 $O(N^3)$ 的预处理。应当使用乘积树进行快速插值，其单行复杂度为 $O(n\log^2(n+1))$。([arXiv][3])
这里的插值点恰好是 $0,1,\ldots,n$，因此权重无需额外求值。令 $M_n(z)=\prod_{j=0}^n(z-j)$，有 $M_n'(j)=(-1)^{n-j}j!(n-j)!$，于是叶子 $j$ 的权重为 $w_j=A_{n,j}(-1)^{n-j}/(j!(n-j)!)$。
在乘积树叶子维护分母 $z-j$ 和分子 $w_j$。合并左右儿子时，分母更新为 $M_LM_R$，分子更新为 $S_LM_R+S_RM_L$。根节点的分子就是 $P_n$。所有行的总插值时间为 $O(N^2\log^2(N+1))$，所得多项式总共只有 $O(N^2)$ 个系数。
然后将询问按 $n$ 分组。设某组有 $T_n$ 个询问，本质上是在 $T_n$ 个给定点上求同一个至多 $n$ 次多项式的值。
使用乘积树与余式树进行快速多点求值：叶子为 $z-m_i$，内部节点维护叶子多项式的乘积；从根开始，将 $P_n$ 对各节点的多项式取模，最后叶子余式就是答案。多点求值和所需的快速取模可以使用标准快速多项式算法。([arXiv][3])
还有一个值得保留的优化：每组询问按至多 $n+1$ 个点分批，而不是为全部 $T_n$ 个点建一棵巨大的树。 一批只需要 $O(n\log^2(n+1))$ 时间，整组的复杂度就是 $O((T_n+n)\log^2(n+1))$，这样对数因子依赖的是 $N$，而不是 $T$。
将所有步骤合并，总时间复杂度为 $O((N^2+T)\log^2(N+1))$。所有询问和答案占用 $O(T)$ 空间，二元系数表与答案多项式占用 $O(N^2)$ 空间；各批次的乘积树可以复用，因此总空间复杂度为 $O(N^2+T)$。
实现时，应先将询问点化为 $m\bmod p$。这是答案关于 $m$ 的多项式性质所保证的，即使原来的 $m\ge p$ 也成立。求值点重复不会影响余式树的正确性，也可以先去重以减少计算。
作为检验，上述公式给出的前几项是 $P_1(m)=m$、$P_2(m)=m(m-1)$、$P_3(m)=m(m-1)^2$，以及 $P_4(m)=m(m-1)(6m^2-11m+10)/6$，分别得到题目样例中的 $2,12,7500$；生成函数结果也与 $n\le6,\ m\le n$ 的直接穷举吻合。
这个算法的两个关键提升是：将三维容斥状态消去，使整张答案表通过二元求逆生成；再将逐询问的线性插值改为离线多点求值。 因而最终复杂度接近于 $N^2$ 个预处理表项与 $T$ 个询问的总规模，而不是仅仅利用 $N=300$ 让三次算法通过。
