HDU7060. Seperated Number

题目链接：HDU7060. Seperated Number

题意：

一个数的分割指将这个数分成连续的部分。

例如，我们可以将\((11)(451)(4)\)​​看作数字\(114514\)​​的一种分割，这是一个含有\(3\)​个部分的分割。

定义一个分割的价值为所有部分数字的和。

例如，分割\((11)(451)(4)\)的价值等于\(11+451+4=466\)。

如果存在一个部分有前导\(0\)​​它也是合法的分割。

现给定数字\(x\)​（无前导\(0\)​​​），问所有不超过\(k\)​个部分的分割的价值和为多少？

答案模\(998244353\)。

分析：

考虑每一位对答案的贡献。

设数字\(x\)​一共有\(n\)​位。

显然满足题目条件的分割方式为，相当于在\(n\)​个位造成的\(n-1\)​个间隙中，插入不多于\(k-1\)​个隔板。

设\(x_i\)​为数字\(x\)​从左往右数（从高位向低位）第\(i\)​​位数字​。

考虑第\(i\)位的贡献，设\(x_i\)在其所在部分的位权为\(10^j\)，显然有\(i+j\leq n\)

此时，分两种情况讨论：

1. 若\(i+j=n\)​，则这个部分应该是分割的最后一部分，不多于\(k-1\)​个隔板可以在\(x_i\)​之前的所有间隙中随意放置，一共有\(i-1\)​可以放的间隙，此时放置的方案数为\(\sum\limits_{m=0}^{k-1}\mathrm{C}_{i-1}^{m}\)​，这种情况的贡献即为\(x_i\cdot 10^{n-i}\sum\limits_{m=0}^{k-1}\mathrm{C}_{i-1}^{m}\)​。
2. 若\(i+j<n\)​​​，这个部分不是分割的最后一部分，所以在\(x_{i+j}\)​​​紧随其后的间隙需要固定放一个隔板，满足位权为\(10^j\)​​​，此时可以放隔板的位置是\(x_i\)​​​之前的所有间隙，以及\(x_{i+j+1}\)​​​后面的所有间隙，所以一共有\(n-j-2\)​​​个间隙可放，最多可放\(k-2\)​​​个隔板（已经用掉一个固定隔板），所以方案数为\(\sum\limits_{m=0}^{k-2}\mathrm{C}_{n-j-2}^{m}\)​​​，这种情况的贡献为\(x_i\cdot \sum\limits_{j=0}^{n-i-1}10^{j}\sum\limits_{m=0}^{k-2}\mathrm{C}_{n-j-2}^{m}\)​​​

我们发现，需要计算组合数下标固定的前缀和。为了方便表示我们设前缀和\(F(i,k)=\sum\limits_{m=0}^{k}\mathrm{C}_{i}^m\)

最终答案可写为\(\sum\limits_{i=1}^{n}\left(x_i\cdot 10^{n-i}F(i-1,k-1)\right)\)​​与\(\sum\limits_{i=1}^{n-1}\left(x_i\cdot \sum\limits_{j=0}^{n-i-1}10^{j}F(n-j-2,k-2)\right)\)​之和。​​​

如果我们能快速计算\(F(i,k)\)​的值，毫无疑问第一部分可以在\(O(n)\)的时间内计算出来。

第二部分，为了快速计算内层求和号，我们仔细观察求和号，发现随着\(i\)​​从\(n-1\)​逐一递减到\(1\)​的时候，\(n-i-1\)​从\(0\)​逐一递增到\(n-2\)​，这说明我们可以轻松维护一个后缀和，只要\(F(i,k)\)​值能够快速计算，后缀和也能快速维护。

现在主要的问题就是\(F(i,k)\)​​如何快速计算，我们发现要计算答案，函数\(F\)的第二个参数我们只需要取\(k-1\)和\(k-2\)。于是算每一个case时可以考虑预处理两个一维数组\(F(i,k-1)\)和\(F(i,k-2)\)，只要在\(O(n)\)​​的时间内预处理，就是胜利。

我们需要寻找递推式，关于组合数我们有杨辉三角形的性质\(\mathrm{C}_{n+1}^{k}=\mathrm{C}_n^k+\mathrm{C}_n^{k-1}\)​，于是考虑错位相加。

\[\begin{aligned} 2F(i,k)&=\sum\limits_{m=0}^{k}\mathrm{C}_{i}^m+\sum\limits_{m=0}^{k}\mathrm{C}_{i}^m\\ &=\sum\limits_{m=0}^{k}\mathrm{C}_{i}^m+\sum\limits_{m=1}^{k+1}\mathrm{C}_{i}^{m-1}\\ &=\mathrm{C}_{i}^0+\sum\limits_{m=1}^{k}\mathrm{C}_{i}^m+\sum\limits_{m=1}^{k}\mathrm{C}_{i}^{m-1}+\mathrm{C}_{i}^{k}\\ &=\mathrm{C}_{i+1}^0+\sum\limits_{m=1}^{k}\mathrm{C}_{i+1}^m+\mathrm{C}_{i}^{k}\\ &=\sum\limits_{m=0}^{k}\mathrm{C}_{i+1}^m+\mathrm{C}_{i}^{k}\\ &=F(i+1,k)+\mathrm{C}_{i}^{k}\\ \\ F(i+1,k)&=2F(i,k)-\mathrm{C}_{i}^{k} \end{aligned} \]

由于组合数能通过预处理阶乘及其逆元\(O(1)\)求得，故\(F(i,k)\)对于给定的\(k\)，可以在\(O(n)\)时间内预处理。

最后的复杂度为\(O(n)\)​。注意答案的第二部分在\(k=1\)的时候贡献为\(0\)​。

代码：

#include <cstdio>
#include <cstring>
typedef long long Lint;
const int maxn = 1e6 + 10;
const Lint mod = 998244353;
Lint fac[maxn], inv_fac[maxn], pow_10[maxn];
Lint F1[maxn], F2[maxn];
Lint fpow(Lint a, Lint b, Lint mod) {
    Lint res = 1;
    for (; b; b >>= 1) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
Lint inv(Lint a, Lint mod) {
    return fpow(a, mod - 2, mod);
}
Lint C(Lint n, Lint k) {
    if (n < 0 || k < 0 || n < k)
        return 0;
    return fac[n] * inv_fac[k] % mod * inv_fac[n - k] % mod;
}
void init() {
    fac[0] = 1;
    for (int i = 1; i <= (int)1e6; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv_fac[(int)1e6] = inv(fac[(int)1e6], mod);
    for (int i = (int)1e6 - 1; i >= 0; i--) {
        inv_fac[i] = inv_fac[i + 1] * (i + 1) % mod;
    }
    pow_10[0] = 1;
    for (int i = 1; i <= (int)1e6; i++) {
        pow_10[i] = pow_10[i - 1] * 10 % mod;
    }
}
char str[maxn];
int main() {
    init();
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, k;
        scanf("%d%s", &k, str + 1);
        n = strlen(str + 1);
        for (int i = 1; i <= n; i++) {
            str[i] -= '0';
        }
        F1[0] = 1;
        for (int i = 1; i <= n; i++) {
            F1[i] = (2 * F1[i - 1] - C(i - 1, k - 1) + mod) % mod;
        }
        F2[0] = k > 1;
        for (int i = 1; i <= n; i++) {
            F2[i] = (2 * F2[i - 1] - C(i - 1, k - 2) + mod) % mod;
        }
        Lint ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += (Lint)str[i] * pow_10[n - i] % mod * F1[i - 1] % mod;
            ans %= mod;
        }
        Lint sum = 0;
        for (int i = n - 1; i >= 1; i--) {
            sum += pow_10[n - i - 1] * F2[i - 1] % mod;
            sum %= mod;
            ans += (Lint)str[i] * sum % mod;
            ans %= mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}