题目
题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=7060
给定一个 (n) 位数 (x)，定义把这个数划分成若干段的代价为每一段的数字之和。求把 (x) 分成不超过 (k) 段的所有方案的代价之和。
(kleq nleq 10^6)，(Qleq 5)。
思路
下文中一个数的第 (i) 位表示从低位到高位的第 (i) 个数字。
分别考虑每一个数字的贡献是不现实的。那么考虑最后的划分中，作为第 (i) 位出现的数字的贡献。
因为 (x) 的第 (i) 位无论怎么划分一定会被算进来，所以我们单独拿出来考虑。剩余可能作为第 (i) 为出现的数就只有第 (i+1sim n) 位的数。
如果 (x) 的第 (j(i<jleq n)) 位在划分中作为第 (i) 位出现了，那么第 (j-i+1) 位和最后一位后面必须划分一次，且第 (j-i+2sim j) 位后面都不能划分。那么相当于剩余的 (n-i-1) 位中可以随意划分不超过 (k-2) 次。
记 (s_i) 表示 (x) 第 (isim n) 位的和，那么作为第 (i) 为出现的数字的贡献为（不计算 (x) 的第 (i) 位的贡献）
[s_{i+1} imes 10^{i-1}left(sum^{k-2}_{j=0}inom{n-i-1}{j}
ight)
]
再考虑 (x) 的第 (i) 位作为划分出来的数的第 (i) 位的贡献。因为第 (n) 位后面必须划分，所以相当于在剩余 (n-i) 位中可以随意划分不超过 (k-1) 次。贡献为
[a_{i} imes 10^{i-1}left(sum^{k-1}_{j=0}inom{n-i}{j}
ight)
]
两个部分加起来就好了。
但是这样时间复杂度是 (O(Qnk)) 的。观察到组合数的前缀和上界都是固定的，也就是相当于每次需要快速求杨辉三角的某一行的前 (k-2)（或 (k-1)）个数字的和，对于 (ileq k-2) 的部分就是 (2^i)，否则可以递推求。
时间复杂度 (O(Qn))。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010,MOD=998244353;
int Q,n,k;
char s[N];
ll a[N],pw[N],pw2[N],fac[N],inv[N];
ll fpow(ll x,ll k)
{
ll ans=1;
for (;k;k>>=1,x=x*x%MOD)
if (k&1) ans=ans*x%MOD;
return ans;
}
ll C(int n,int m)
{
if (n<m) return 0;
return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main()
{
fac[0]=inv[0]=pw[0]=pw2[0]=1;
for (int i=1;i<N;i++)
{
fac[i]=fac[i-1]*i%MOD;
pw[i]=pw[i-1]*10LL%MOD;
pw2[i]=pw2[i-1]*2LL%MOD;
}
inv[N-1]=fpow(fac[N-1],MOD-2);
for (int i=N-2;i>=1;i--)
inv[i]=inv[i+1]*(i+1)%MOD;
scanf("%d",&Q);
while (Q--)
{
scanf("%d%s",&k,s+1);
n=strlen(s+1);
for (int i=1;i<=n;i++)
a[i]=(a[i-1]+s[i]-48)%MOD;
if (k==1)
{
ll sum=0;
for (int i=1;i<=n;i++)
sum=(10LL*sum+s[i]-48)%MOD;
cout<<sum<<"
";
continue;
}
ll ans=0,sum=pw2[k-2];
for (int i=n-1;i>=1;i--)
if (n-i-1<=k-2)
ans=(ans+1LL*a[n-i]*pw[i-1]%MOD*pw2[n-i-1])%MOD;
else
{
sum=(sum*2LL-C(n-i-2,k-2))%MOD;
ans=(ans+1LL*a[n-i]*pw[i-1]%MOD*sum)%MOD;
}
sum=pw2[k-1];
for (int i=n;i>=1;i--)
if (n-i<=k-1)
ans=(ans+1LL*(a[n-i+1]-a[n-i])*pw[i-1]%MOD*pw2[n-i])%MOD;
else
{
sum=(sum*2LL-C(n-i-1,k-1))%MOD;
ans=(ans+1LL*(a[n-i+1]-a[n-i])*pw[i-1]%MOD*sum)%MOD;
}
cout<<(ans%MOD+MOD)%MOD<<"
";
}
return 0;
}