[Medium] AT_abc390_g [ABC390G] Permutation Concatenation

简要题意

对于一个排列 $p$，定义 $f(p)$ 表示排列的每一个数按顺序依次拼接得到的十进制数。

你需要计算对于所有长度为 $n$ 的排列 $p$ 的 $f(p)$ 之和。答案对 $998,244,353$ 取模。

$1\leq n\leq 2\times 10^5$。

思路

约定几个符号：

• $\lambda(x)=\lfloor\lg x\rfloor+1$ 也就是 $x$ 在十进制下的数位数。
• $\Lambda(x)=10^{\lambda(x)}$。

先拆贡献，记 $\rho(x)$ 为 $x$ 的贡献，则有：

$$\rho(x)=\sum_{i=0}^{n-1}i!(n-i-1)!\cdot [z^i]\prod_{j\in[1,n],j\neq x} (1+\Lambda(j)z)$$

即枚举 $x$ 为倒数第 $i+1$ 个数，然后钦定后面 $i$ 个数的选法（那么前面的选法也就随之确定了，最后注意要乘上的不是方案数而是移位贡献），最后乘上阶乘表示顺序。最后答案就是 $\sum_i i\rho(i)$。

考察：

$$\begin{aligned} \mathbf{F}(z)&=\prod_{i=1}^{n} (1+\Lambda(i)z)\\ &=\exp\left(\sum_{i=1}^{n}\ln(1+\Lambda(i)z)\right)\\ &=\exp\left(-\sum_{i=1}^{n}\sum_{j\geq 1} \frac{(-1)^j}{j} (\Lambda(i)z)^j\right)\\ &=\exp\left(-\sum_{j\geq 1}\frac{(-1)^j}{j}z^j\sum_{i=1}^{n}\Lambda^j(i)\right)\\ &=\exp\left(-\sum_{j\geq 1}\frac{(-1)^j}{j}z^j\sum_{i=1}^{\lambda(n)}10^{ij}\sum_{k=1}^{n}[\lambda(k)=i]\right) \end{aligned}$$

于是可以 $O(n\log n)$ 求出 $\mathbf{F}(z)$。

然后我们考虑原式：

$$\rho(x)=\sum_{i=0}^{n-1}i!(n-i-1)!\cdot [z^i](\mathbf{F}(z)\cdot (1+\Lambda(x)z)^{-1})$$

注意到自变量其实可以改为 $\lambda(x)$，于是定义 $\rho(x)=\Rho(\lambda(x))$：

$$\Rho(x)=\sum_{i=0}^{n-1}i!(n-i-1)\cdot (1+10^xz)^{-1})$$

于是我们只需要高效求出 $[z^i](\mathbf{F}(z)\cdot (1+10^xz)^{-1})$ 即可。

注意到 $(1+10^xz)^{-1}=\sum_{i\geq 0}(-10^x)^iz^i$，直接卷积即可。时间复杂度 $O(n\log^2 n)$。

代码

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

/* hide poly template */

using poly::Poly;

constexpr int mod = 998244353;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

int fastpow(int x, int y){
    int ret = 1;
    for(;y;y>>=1,x=Mul(x, x)){ if(y & 1) ret = Mul(ret, x); }
    return ret;
}

const int N = 2e5 + 5;
int n, m, cnt[N], fact[N], cnts[N];

int lambda(int x){ return floor(log10(x)) + 1; }

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++) cnt[lambda(i)]++, cnts[lambda(i)] = Add(cnts[lambda(i)], i);
    fact[0] = 1, m = lambda(n);
    for(int i=1;i<=n;i++) fact[i] = Mul(fact[i - 1], i);
    Poly f; f.resize(n + 1);
    for(int j=1;j<=n;j++){
        int tmp = 0;
        for(int i=1;i<=m;i++) tmp = Add(tmp, Mul(fastpow(10, i * j), cnt[i]));
        f[j] = Mul(Mul((j & 1 ? 1 : mod - 1), fastpow(j, mod - 2)), tmp);
    }
    f = f.exp();
    int ans = 0;
    for(int i=1;i<=m;i++){
        Poly g; g.resize(n + 1);
        int tmp = mod - fastpow(10, i);
        for(int j=0;j<=n;j++) g[j] = fastpow(tmp, j);
        g = f * g;
        int ret = 0;
        for(int j=0;j<n;j++) ret = Add(ret, Mul(Mul(fact[j], fact[n - j - 1]), g[j]));
        ans = Add(ans, Mul(ret, cnts[i]));
    }
    cout << ans << '\n';
    return 0;
}

// Written by xiezheyuan

Submission。