[ABC288F] Integer Division 题解
spider_oyster
·
·
题解
考虑 DP，f_{i} 表示考虑到 X 的第 i 位分法之和；
并设 s(i,j) 表示 X 的 i 到 j 位组成的数字。
则 f_{i}=\sum_{j=0}^{i-1}f_{j} \times s(j+1,i)。
但这样时间复杂度是 n^2 的，所以得优化一下。
有求和，自然往前缀和上靠，又发现 s(j+1,i)=s(j+1,i-1)\times10+X[i]。
所以状态转移方程可以写成：
仔细观察前面那一项，当 $j=i-1$ 的时候，$s(j+1,i-1)=s(i,i-1)$，这种情况不存在，不用考虑，故：
$\sum_{j=0}^{i-1}f_{j} \times s(j+1,i-1)\times 10=\sum_{j=0}^{i-2}f_{j} \times s(j+1,i-1)\times 10=f_{i-1} \times 10$。
所以状态转移方程进一步写为：
$f_{i}=f_{i-1}\times 10+\sum_{j=0}^{i-1}f_{j}\times X_{i}$。
这道题就这么愉快的解决了！
```
#include<bits/stdc++.h>
#define F(i,s,t) for(register int i=(s);i<=(t);++i)
#define R(i,s,t) for(register int i=(s);i>=(t);--i)
#define ll long long
using namespace std;
const int N=2e5+15;
const int p=998244353;
int n;
ll f[N],sum;
char s[N];
int main()
{
scanf("%d%s",&n,s+1);
f[0]=1,f[1]=s[1]-'0';
sum=f[0]+f[1];
F(i,2,n)
{
f[i]=(f[i-1]*10%p+sum*(s[i]-'0')%p)%p;
sum=(sum+f[i])%p;
}
cout<<f[n];
}
```