题目描述

难度分:$2024$

输入$n(2 \leq n \leq 200000)$以及有$n$个数位的数字$s$，保证$s$不含$0$。

把$s$分割成若干段，得分为每一段的乘积。特别地，如果不分割，则得分为$s$。

输出所有分割方案的得分之和，模$998244353$。

注：一共有$2^{n-1}$种分割方案。

输入样例$1$

3
234

输出样例$1$

418

输入样例$2$

4
5915

输出样例$2$

17800

输入样例$3$

9
998244353

输出样例$3$

258280134

算法

动态规划

这个题肯定需要计算每个划分出来的段对答案的贡献，不然枚举所有的$2^{n-1}$种划分方案必然会超时。

状态定义

$dp[i]$表示划分$s[1:i]$的所有划分方案得分之和。

状态转移

枚举前一个分割点$j$，那么$s[j+1:i]$就能划分出一个数字，状态转移方程为

$dp[i]=\Sigma_{j=0}^{j=i-1} dp[j] \times s[j+1:i]$

但是这样枚举的话时间复杂度为$O(n^2)$会超时，因此可以将这个式子变形。

$dp[i+1]$

$=\Sigma_{j=0}^{j=i} dp[j] \times s[j+1:i+1]$

$=\Sigma_{j=0}^{j=i} dp[j] \times (s[j+1:i] \times 10 + s[i+1])$

$=10\Sigma_{j=0}^{j=i} dp[j] \times s[j+1:i]+\Sigma_{j=0}^{i}dp[j] \times s[i+1]$

由于$j=i$时，$s[j+1:i]$不存在，所以$\Sigma_{j=0}^{j=i} dp[j] \times s[j+1:i]=\Sigma_{j=0}^{j=i-1} dp[j] \times s[j+1:i]$，于是有如下状态转移方程。

$dp[i+1]=10dp[i]+\Sigma_{j=0}^{i}dp[j] \times s[i+1]$

这样一来就可以一边递推一边维护个$dp$数组的前缀和来$O(1)$地求第二项。

复杂度分析

时间复杂度

只有从$1$遍历到$n$一重循环，因此时间复杂度为$O(n)$，是线性的。

空间复杂度

开辟了一个$dp$数组，与$s$同规模，额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 200010, MOD = 998244353;
LL dp[N];
int n;
char s[N];

int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);
    dp[0] = 0;
    LL presum = 1;
    for(int i = 1; i <= n; i++) {
        int d = s[i] - '0';
        dp[i] = (10ll*dp[i - 1]%MOD + presum*d%MOD)%MOD;
        presum = (presum + dp[i]) % MOD;
    }
    printf("%d\n", dp[n]);
    return 0;
}