题解 CF1349F2 【Slime and Sequences (Hard Version)】

· · 题解

题目描述

定义一个正整数序列为好序列，当且仅当如果某个数 k 出现过，那么一定有 k-1 在最后一个 k 的前面出现过。

对于所有 i\in[1,n]，求出 i 在所有好序列中出现次数的和

Easy Version:n\leq 5000

Hard Version:n\leq 10^5

题解

领略到了国际计数顶尖水平。。

问题转化

有重复元素的正整数序列不好统计，我们试图将它映射到排列上

我们构建一个排列 p，在相邻两个数字之间填入不等号，设 p_{1\dots i} 中共有 num_i 个小于号，我们将它映射到 a 序列：a_{p_i}=num_i+1，则 a 是一个好序列

证明如下：设 i 为一个小于号右边的位置，则 num_{i-1}+1=num_i，即 a_{p_{i-1}}+1=a_{p_i}，而由于是小于号，所以 p_{i-1}<p_i，容易发现这正是题目中要求的限制

而对于一个好序列，我们从小到大枚举数值，对于每一个数值，我们将它所在的所有下标从大到小放到数列的后面（初始数列为空），这样我们就完成了从好序列到排列的映射

则容易发现，这是一个双射关系

排列组合推导

这里引入欧拉数：\left<\begin{matrix}n\\k\end{matrix}\right> 表示长度为 n 的排列中，相邻数字之间的小于号数目为 k 的方案数

设 ans_k 为数字 k+1 的答案

则 ans_k=\sum\limits_{i=\max(k,1)}^n\left<\begin{matrix}i\\k\end{matrix}\right>\dbinom ni(n-i)!

什么意思呢？我们枚举产生好序列中 k+1 这个数字的位置，则前 i 个数中需要有 k 个小于号，我们再给前 i 个数分配标号，剩下的 n-i 个数随意排列

可是这个算的是排列方案数，而且还算重了

我们考虑证明算重的次数就等于该方案中 k+1 的出现次数：对于一个排列，它被计算当且仅当 i 在第 k 个小于号和第 k+1 个小于号之间，而这恰好就是 k+1 的出现次数

## 优化 我们假装不会欧拉数的通项式（其实是因为它的通项式不容易继续优化？），使用容斥代替掉欧拉数 设 $\begin{vmatrix}n\\k\end{vmatrix}$ 表示长度为 $n$ 的排列，至少有 $k$ 个小于号的方案数 容易发现，$\begin{vmatrix}n\\k\end{vmatrix}=\sum\limits_{i=k}^n\dbinom ik\left<\begin{matrix}n\\i\end{matrix}\right>

二项式反演一下可以得到：\left<\begin{matrix}n\\k\end{matrix}\right>=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom ik\begin{vmatrix}n\\i\end{vmatrix}

考虑计算 \begin{vmatrix}n\\k\end{vmatrix}，我们将小于号视为一条边，则至少有 n-k 个连通块，这些连通块内的顺序是确定的，因为是用小于号连接的

由于是排列问题，则答案为每个块的 \mathbf{EGF} 卷起来

每个块的 \mathbf{EGF} 为 \mathbf{EGF\{[0,1,1,\cdots]\}}=e^x-1，为什么常数项为 0？一个块至少要有一个数字嘛

则 \begin{vmatrix}n\\k\end{vmatrix}=n![x^n](e^x-1)^{n-k}

代入可得（ans_0 特判一下，下面就没有 \max(k,1)了）：

ans_k&=\sum\limits_{i=k}^n\dbinom ni(n-i)!\sum\limits_{j=k}^i(-1)^{j-k}\dbinom jki![x^i](e^x-1)^{i-j}\\ &=\sum\limits_{i=k}^n\dbinom ni(n-i)!i!\sum\limits_{j=k}^i(-1)^{j-k}\dbinom jk[x^i](e^x-1)^{i-j}\\ &=n!\sum\limits_{i=k}^n\sum\limits_{j=k}^i(-1)^{j-k}\dbinom jk[x^i](e^x-1)^{i-j}\\ &=n!\sum\limits_{j=k}^n(-1)^{j-k}\dbinom jk\sum\limits_{i=j}^n[x^i](e^x-1)^{i-j}\\ &=\dfrac{n!}{k!}\sum\limits_{j=k}^n\dfrac{(-1)^{j-k}j!}{(j-k)!}\sum\limits_{i=j}^n[x^i](e^x-1)^{i-j}\\ \end{aligned}

设 R_j=\sum\limits_{i=j}^n[x^i](e^x-1)^{i-j}

ans_k&=\dfrac{n!}{k!}\sum\limits_{j=k}^n\dfrac{(-1)^{j-k}j!}{(j-k)!}R_j\\ &=\dfrac{n!}{k!}\sum\limits_{j=k}^n\dfrac{(-1)^{j-k}}{(j-k)!}\times R_j\cdot j! \end{aligned}

这是一种特殊的卷积，求法参见关于一类特殊卷积的求法

问题转化为求出序列 R

我们发现 R_k 的定义式很难看，每一次取的系数都不是同一项的，把它改得漂亮一点：

R_k&=\sum\limits_{i=k}^n[x^i](e^x-1)^{i-k}\\ &=\sum\limits_{i=k}^n[x^k](\dfrac{e^x-1}x)^{i-k}\\ &=\sum\limits_{i=0}^{n-k}[x^k](\dfrac{e^x-1}{x})^i \end{aligned}

把它化成封闭形式，设 F(x)=\dfrac{e^x-1}{x}：

R_k&=\sum\limits_{i=0}^{n-k}[x^k]F^i(x)\\ &=[x^k]\left(\dfrac{1-F^{n-k+1}(x)}{1-F(x)}\right)\\ &=[x^k]\dfrac{1}{1-F(x)}-[x^k]\dfrac{F^{n-k+1}(x)}{1-F(x)} \end{aligned}

对于前一项，我们可以多项式求逆，但是发现分母常数项为 0，不能直接求逆

那怎么做呢？我们转为求 \dfrac{1}{(1-F(x))\cdot x^{-1}}\cdot x^{-1}，这样就可以避免常数项为 0 的问题了（由于该式中分母一次项不为 0，所以乘上 x^{-1} 表示左移一位）

对于正确性的说明，需要引入抽象代数中的分式环（分式域）概念，不展开了，可以百度搜索拉格朗日反演学习一下

则我们只需要求出后一项就做完了，设 S_k=[x^k]\dfrac{F^{n-k+1}(x)}{1-F(x)}

我们发现 S_k 很不优美，对于每一个 k，它的多项式长得都不一样，这样我们不可能在低于 O(n^2) 的时间复杂度内求出

所以我们考虑引入一个新的限制 y，并消除 x 的影响：

S_k&=[x^k]\dfrac{F^{n-k+1}(x)}{1-F(x)}\\ &=[x^{n+1}]\dfrac{(xF(x))^{n-k+1}}{1-F(x)}\\ &=[x^{n+1}y^{n-k+1}]\sum\limits_{i=0}^{\infty}\dfrac{(xF(x))^{i}}{1-F(x)}\\ &=[x^{n+1}y^{n-k+1}]\dfrac{1}{1-F(x)}\cdot\dfrac{1}{1-xF(x)y}\\ \end{aligned}

即求出右面多项式 [x^{n+1}] 项关于 y 的多项式，容易联想到多项式复合科技

但是不太行，因为 1-xF(x)y 中不仅有 F(x) 还有 x

考虑构造两个函数 H(x),W(x)，使得 H(W(x))=\dfrac{1}{1-F(x)}\cdot\dfrac{1}{1-xF(x)y}

再构造一个函数 G(x)，使得 G(W(x))=x，这样我们就可以使用扩展拉格朗日反演求解了

构造如下：

W(x)=xF(x)

设 M(W(x))=F(x)，即我们使用 M(x) 和 W(x) 复合来消除 W(x) 中的 x

则 \dfrac{1}{1-F(x)}\cdot\dfrac{1}{1-xF(x)y}=\dfrac{1}{1-M(W(x))}\cdot\dfrac{1}{1-W(x)y}

若要使得 H(W(x))=\dfrac{1}{1-F(x)}\cdot\dfrac{1}{1-xF(x)y}，联系上一个式子，容易构造出 H(x)=\dfrac{1}{1-M(x)}\cdot \dfrac{1}{1-xy}

最后是 G(x)，这个很简单，G(x)=\dfrac{x}{M(x)}，因为此时 G(W(x))=\dfrac{xF(x)}{F(x)}=x

以上，我们构造出了拉格朗日反演所需的所有函数，直接套用扩展拉格朗日反演公式可得：

[x^{n+1}]H(W(x))=\dfrac1{n+1}[x^n]H'(x)\left(\dfrac{x}{G(x)}\right)^{n+1}

暴力计算 H'(x)=\dfrac{y(1-M(x))+(1-xy)M'(x)}{(1-M(x))^2(1-xy)^2}，代入：

[x^{n+1}]H(W(x))&=\dfrac1{n+1}[x^n]\dfrac{y(1-M(x))+(1-xy)M'(x)}{(1-M(x))^2(1-xy)^2}\cdot M^{n+1}(x)\\ &=\dfrac1{n+1}[x^n]\left(\dfrac{y}{(1-M(x))(1-xy)^2}+\dfrac{M'(x)}{(1-M(x))^2(1-xy)}\right)\cdot M^{n+1}(x) \end{aligned}

写到这里，公式已经不能看了 qwq，我们把关于 y的封闭形式展开，这样我们就可以提取出 y 的某一项啦

[x^{n+1}]H(W(x))&=\dfrac1{n+1}[x^n]\left(\dfrac1{1-M(x)}\sum\limits_{i=0}^{\infty}(i+1)x^iy^{i+1}+\dfrac{M'(x)}{(1-M(x))^2}\sum\limits_{i=0}^{\infty}x^iy^i\right)\cdot M^{n+1}(x)\\ \end{aligned}

我们提取出第 m 项（S_k 需要的即第 n-k+1 项）：

&\dfrac1{n+1}[x^ny^m]\left(\dfrac1{1-M(x)}\sum\limits_{i=0}^{\infty}(i+1)x^iy^{i+1}+\dfrac{M'(x)}{(1-M(x))^2}\sum\limits_{i=0}^{\infty}x^iy^i\right)\cdot M^{n+1}(x)\\ =&\dfrac1{n+1}[x^n]\left(\dfrac{mx^{m-1}}{1-M(x)}+\dfrac{M'(x)x^m}{(1-M(x))^2}\right)\cdot M^{n+1}(x)\\ =&\dfrac1{n+1}\left([x^{n-m+1}]m\dfrac{M^{n+1}(x)}{1-M(x)}+[x^{n-m}]\dfrac{M'(x)M^{n+1}(x)}{(1-M(x))^2}\right) \end{aligned}

发现出现了和上面同样的问题：分母的常数项为 0，我们同上面一样转化一下：

=\dfrac1{n+1}[x^{n-m+2}]\left(m\dfrac{M^{n+1}(x)}{(1-M(x))x^{-1}}+\dfrac{M'(x)M^{n+1}(x)}{((1-M(x))x^{-1})^2}\right)

突然发现我们还没有求 M(x)=\dfrac x{G(x)}

G(W(x))=G(e^x-1)=x$，容易构造出 $G(x)=\ln(x+1)

则 M(x)=\dfrac x{\ln(x+1)}

最终时间复杂度 O(n\log n)

真是一道休闲的好题呢

代码的多项式板子可以参照我博客置顶的多项式全家桶

int fac[N],ifac[N];
void init(int n)
{
    fac[0] = 1;for(int i = 1;i <= n;i++) fac[i] = (ll)fac[i - 1] * i % mod;
    ifac[n] = qpow(fac[n],mod - 2);for(int i = n;i;i--) ifac[i - 1] = (ll)ifac[i] * i % mod;
}
int n,m,t1[N],t2[N],S[N];
int H[N],H1[N],H2[N],inv[N];
int ans[N];
int main()
{
    n = read(),m = n + 2;init(n + 2);
    for(int i = 0;i < n + 1;i++) t1[i] = mod - ifac[i + 2];
    Inv(t1,S,n + 1);for(int i = 0;i < n;i++) S[i] = S[i + 1];
    memset(t1,0,sizeof(t1));t1[0] = t1[1] = 1;Ln(t1,t2,m + 2);
    for(int i = 0;i < m + 1;i++) t1[i] = t2[i + 1];
    Inv(t1,H,m + 1);
    Power(H,H1,m + 1,"",n + 1);
    Der(H,t1,m + 1);Mul(t1,H1,H2,m + 1,m + 1);
    for(int i = 0;i < m;i++) t1[i] = mod - H[i + 1];
    Inv(t1,inv,m);
    Mul(H1,inv,H1,m,m),Mul(H2,inv,H2,m,m),Mul(H2,inv,H2,m + 1,m);
    int invn = qpow(n + 1,mod - 2);
    for(int k = 0;k < n;k++)
    {
        int m = n - k + 1;
        reduce(S[k] -= ((ll)H1[n - m + 2] * m + H2[n - m + 2]) % mod * invn % mod);
    }S[0]--;
    memset(t1,0,sizeof(t1)),memset(t2,0,sizeof(t2));
    for(int i = 0;i < n;i++)
        if(i & 1) t1[n - i - 1] = mod - ifac[i];
        else t1[n - i - 1] = ifac[i];
    for(int i = 0;i < n;i++)
        t2[i] = (ll)S[i] * fac[i] % mod;
    Mul(t1,t2,ans,n,n);
    for(int i = 0;i < n;i++) pprint((ll)ans[i + n - 1] * ifac[i] % mod * fac[n] % mod);
    return 0;
}