[数学记录]ARC112E Cigar Box

**题意** ： 有序列 $A_{1\sim n}$ ，初始时为 $\{1\sim n\}$ ，执行下列操作 $m$ 次： - 选择一个元素，将其移到开头或结尾。 给出最终的 $A_{1\sim n}$ ，求出可能的操作方案数。答案对 $998244353$ 取模。 $n,m\leq 3000$ ，时限$\texttt{2s}$。 ------------ 若一个元素被操作了多次，那么显然只有最后一次操作有实际效果。 对于一个操作序列，我们对每个元素只保留最后一次操作，称作简化操作序列。 观察反射，对于一个长为 $k(\leq m)$ 的简化操作序列，可以向其中插入若干无效操作，显然方案数只和 $k$ 有关。 具体地，操作序列要求 $k$ 个元素都存在，数值部分的方案数是 $\begin{Bmatrix}m\\k\end{Bmatrix}k!$ ；此外还有方向部分，对于 $k$ 个有效操作，方向确定，其余操作可以随意，方案数为 $2^{m-k}$。 注意到我们钦定了 $k$ 种元素最后出现的顺序，故方案数还需除以 $k!$ 。 接下来我们只需对简化操作序列计数。 ------------ 记被“移开头”的集合为 $S_l$ ，“移结尾”的集合为 $S_r$ ，则最后效果相当于 $S_l$ 在左侧随意打乱，接上剩余的元素（按原序，即递增），然后 $S_r$ 在右侧随意打乱。 我们找出排列中的一个递增区间 $[l,r]$，然后就能确定 $S_l=A_{1\sim l-1},S_r=A_{r+1\sim n}$ 。 此时简化操作序列长为 $l-n+n-r$ 。能根据 $S_l,S_r$ 确定前后两个方向操作的顺序，但它们可以随意归并，方案数为 $\dbinom{l-1+n-r}{l-1}$ 。 枚举递增区间即可。 复杂度为 $O(\max(n,m)^2)$。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 3050 using namespace std; const int mod=998244353; int C[MaxN][MaxN],S[MaxN][MaxN],pw2[MaxN]; void Init(int n) { S[0][0]=C[0][0]=pw2[0]=1; for (int i=1;i<=n;i++){ pw2[i]=(pw2[i-1]<<1)%mod; C[i][0]=1; for (int j=1;j<=i;j++){ C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; S[i][j]=(1ll*j*S[i-1][j]+S[i-1][j-1])%mod; } } } int n,m,a[MaxN],o[MaxN]; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++)scanf("%d",&a[i]); Init(max(n,m)); o[n]=pw2[n]; for (int l=1;l<=n;l++) for (int r=l;r<=n;r++){ int k=l-1+n-r; o[k]=(o[k]+C[k][l-1])%mod; if (a[r+1]<a[r])break; } int ans=0; for (int k=0;k<=min(n,m);k++) ans=(ans+1ll*S[m][k]*pw2[m-k]%mod*o[k])%mod; printf("%d",ans); return 0; } ``` 所用的斯特林数可以卷积 $O(n\log n)$ 求出。 记 $o_k$ 为长为 $k$ 的简化操作序列数。 记 $A_i>A_{i+1}$ 的 $i$ 为坏间隔，将整个序列划分为极长递增区间。极长递增区间的所有子区间恰组成递增区间集合。 记某个极长递增区间为 $[l,r]$ ，考虑其长为 $k$ 的子区间的贡献： $$o_{n-k}\leftarrow \sum\limits_{i=l}^{r-k+1}\dbinom{n-k}{i-1}$$ 注意到 $k$ 每减小 $1$ ，在上标增大 $1$ 的同时边界也扩大 $1$ ，这样的组合数部分和可以递推。 综上，本题的复杂度可以做到 $O(n\log n)$。