2022 年牛客多校加赛场 L 题题解

L Lndjy and the mex

题意：给定长度为 $nn$ 的序列 $\{a_i\}\backslash \{a\_i\backslash \}$，满足 $\sum a_i=n\backslash sum\; a\_i=n$。问由 $a_{0}a\_0$ 个 $00$，$a_{1}a\_1$ 个 $11$，……，$a_{n}a\_n$ 个 $nn$ 构成的全部 ${\displaystyle \frac{n!}{\prod _{i=0}^n{a}_i!}}\backslash displaystyle\; \backslash dfrac\{n!\}\{\backslash prod\_\{i=0\}^n\; a\_i!\}$ 个序列中，每个序列的全部连续子序列的 $\mathrm{m}\mathrm{e}\mathrm{x}\backslash rm\; mex$ 值之和。$n\le 1\times 10^{5}n\; \backslash leq\; 1\backslash times\; 10^5$。

解法：显然直接求 $\mathrm{m}\mathrm{e}\mathrm{x}\backslash rm\; mex$ 是非常不好做的，尝试将其转化为方案数。设 $f_{i}f\_i$ 表示连续子序列的 $\mathrm{m}\mathrm{e}\mathrm{x}\backslash rm\; mex$ 值为 $ii$ 的连续子序列个数，则答案为 ${\displaystyle \sum _{i=0}^{+\mathrm{\infty }}i{f}_i}\backslash displaystyle\; \backslash sum\_\{i=0\}^\{+\backslash infty\}if\_i$，令 ${\displaystyle g_i=\sum _{j=i}^{+\mathrm{\infty }}{f}_j}\backslash displaystyle\; g\_i=\backslash sum\_\{j=i\}^\{+\backslash infty\}f\_j$，则有：

以上的化简是用到了 $g_{+\mathrm{\infty }}=0g\_\{+\backslash infty\}=0$。

注意到 $g_{i}g\_i$ 的组合意义为，连续子序列 $\mathrm{m}\mathrm{e}\mathrm{x}\backslash rm\; mex$ 值大于等于 $ii$ 的序列个数，等价于 $0\sim i-10\; \backslash sim\; i-1$ 的数字至少出现一次，其余数字随意的方案数。考虑到每个数字选了多少个，假设第 $ii$ 个数字选了 $b_{i}b\_i$ 个，那么有：

即首先是连续子序列内部的排列，再是外部的排列，最后再将这个连续子序列插入完整的序列。那么这个问题就可以非常容易的使用 EGF 得到解决：设 $f_i(x)f\_i(x)$ 表示数字 $ii$ 的选择方案的 EGF，${\displaystyle f_i(x)=\sum _{j=0}^{a_i}\frac{x^j}{j!(a_i-j)!}}\backslash displaystyle\; f\_i(x)=\backslash sum\_\{j=0\}^\{a\_i\}\backslash dfrac\{x^j\}\{j!(a\_i-j)!\}$，$g_i(x)=f_i(x)-{\displaystyle \frac{1}{a_i!}}g\_i(x)=f\_i(x)-\backslash dfrac\{1\}\{a\_i!\}$ 表示至少选一个的方案，则最终的答案为：

注意：此处和通常的 EGF 稍有区别。正常的 EGF 由于不考虑外侧的排列，为 ${\displaystyle f_i(x)=\sum _{j=0}^{a_i}\frac{x^j}{j!}}\backslash displaystyle\; f\_i(x)=\backslash sum\_\{j=0\}^\{a\_i\}\backslash dfrac\{x^j\}\{j!\}$。而当选定连续子序列中数字个数确定，外侧也随之确定，他们的排列数为 ${\displaystyle \frac{(n-s+1)!}{(a_i-j)!}}\backslash dfrac\{(n-s+1)!\}\{(a\_i-j)!\}$，因而可以将此系数杂糅进 $f_i(x)f\_i(x)$。

考虑使用分治 NTT 去计算上式：对于区间 $(l,r)(l,r)$ 维护 ${\displaystyle F_1(x,l,r)=\prod _{i=l}^r{g}_i(x),F_2(x,l,r)=\prod _{i=l}^r{f}_i(x),F_3(x,l,r)=\sum _{i=l}^{r-1}\prod _{j=l}^i{g}_i(x)\prod _{j=i+1}^r{f}_i(x)}\backslash displaystyle\; F\_1(x,l,r)=\backslash prod\_\{i=l\}^rg\_i(x),F\_2(x,l,r)=\backslash prod\_\{i=l\}^rf\_i(x),F\_3(x,l,r)=\backslash sum\_\{i=l\}^\{r-1\}\backslash prod\_\{j=l\}^\{i\}g\_i(x)\backslash prod\_\{j=i+1\}^rf\_i(x)$，则有 $F_3(x,l,r)=F_1(x,l,m)F_3(x,m+1,r)+F_3(x,l,m)F_2(x,m+1,r)-F_1(x,l,m)F_2(x,m+1,r)F\_3(x,l,r)=F\_1(x,l,m)F\_3(x,m+1,r)+F\_3(x,l,m)F\_2(x,m+1,r)-F\_1(x,l,m)F\_2(x,m+1,r)$。因而可以 $\mathcal{O}(n{}^{2}n)\backslash mathcal\; O(n\backslash log^2n)$ 的通过。

Poly f[N + 5], g[N + 5], gf[N + 5];
int a[N + 5];

void build(int place, int left, int right)
{
    if (left == right)
    {
        f[place].resize(a[left] + 1);
        for (int i = 0; i <= a[left]; i++)
            f[place][i] = 1ll * ifac[i] * ifac[a[left] - i] % P;
        g[place] = f[place];
        g[place][0] = 0;
        gf[place] = f[place] + g[place];
        return;
    }
    int mid = (left + right) >> 1;
    build(place << 1, left, mid);
    build(place << 1 | 1, mid + 1, right);
    f[place] = f[place << 1] * f[place << 1 | 1];
    g[place] = g[place << 1] * g[place << 1 | 1];
    gf[place] = g[place << 1] * gf[place << 1 | 1] + gf[place << 1] * f[place << 1 | 1] - g[place << 1] * f[place << 1 | 1];
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i <= n;i++)
        scanf("%d", &a[i]);
    build(1, 0, n);
    Poly F = gf[1] - f[1];
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = (ans + 1ll * (n - i + 1) * fac[i] % P * fac[n - i] % P * F[i]) % P;
    printf("%d", ans);
    return 0;
}