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\)
此时，分两种情况讨论：
- 若\(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}\)。
- 若\(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;
}