# [APC001] E - Linear Map

## 题目背景

**请注意本题的特殊时间限制，并酌情使用较快的输入输出方式**。

在广阔的 florr 世界中，有一个不为人知的角落，它的建立是为了方便快速测试新 mob，而现在它被废弃了，但没有消失。

冒险者 MF 找到了这里，并发现其名字为：Linear map。

## 题目描述

Linear map 可看作一个字符串，每个字符都是一个 $0\sim 9$ 的数字。

MF 认为，如果一个字符串存在两段长度均 $>1$ 的不同区间的和相同，那么该字符串是无趣的。

比如，$3421$ 就是无趣的字符串，因为 $3+4=4+2+1$，而 $5023$ 也是无趣的字符串，因为 $5+0=2+3$。相反，$13$ 和 $285$ 都不是无趣的字符串。

MF 打算将 Linear map 划分为若干非空连续且不重复的子段，这些子段包含了整个字符串的所有字符，且满足每个子段都不是无趣的字符串。

MF 是一个有趣的人，于是它想算出划分的方案数，并对 $998244353$ 取模。

## 输入格式

一行一个字符串 $s$。

## 输出格式

一行一个整数表示答案对 $998244353$ 取模后的结果。

## 样例 #1

### 样例输入 #1

```
453
```

### 样例输出 #1

```
4
```

## 样例 #2

### 样例输入 #2

```
3333
```

### 样例输出 #2

```
5
```

## 样例 #3

### 样例输入 #3

```
9475739582850286
```

### 样例输出 #3

```
9360
```

## 提示

### 样例解释

- 样例 $\tt\#1$
	
所有划分均合法：$\{453\},\{45,3\},\{4,53\},\{4,5,3\}$。

- 样例 $\tt\#2$
	
合法方案为：$\{33,33\},\{33,3,3\},\{3,33,3\},\{3,3,33\},\{3,3,3,3\}$。

### 数据范围

对于 $100\%$ 的数据，满足 $1\le |s|\le 1.5\times 10^7$，且 $s$ 中仅包含数字。

以下代码 TLE 了可以优化吗，长度 19 是必要的吗

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int MOD = 998244353;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    cin >> s;
    int n = s.size();
    
    // Initialize DP array
    // Using a vector of unsigned ints for DP
    // dp[i] represents the number of ways to partition the first i characters
    // Initialize with 0 and set dp[0] =1
    vector<int> dp(n +1, 0);
    dp[0] =1;
    
    // Precompute prefix sums if needed (not required here)
    
    for(int i=0; i <n; ++i){
        if(dp[i] ==0){
            continue;
        }
        
        // Initialize bitmask for seen sums
        // Using 3 unsigned long longs to cover up to 192 bits
        // sum_max = 171, so 192 bits are enough
        ull seen0 =0, seen1=0, seen2=0;
        
        // List to store sums of all substrings ending at current position
        // To optimize, use a temporary list with a fixed size
        // Maximum number of substrings ending at current position is 19
        // Initialize an array to store current sums
        int max_l = min(19, n -i);
        // Use a vector to store current sums, initialize empty
        // To optimize, use a separate array and keep track of its size
        int current_size =0;
        int current_sums[19] = {0};
        
        bool duplicate_found = false;
        
        for(int l=1; l<=max_l; ++l){
            char c = s[i + l -1];
            int digit = c - '0';
            
            // Update current_sums: add digit to all existing sums
            // and add a new sum starting with this digit
            // Traverse from end to start to avoid overwriting
            for(int j = current_size -1; j >=0; --j){
                current_sums[j] += digit;
            }
            
            // Add new sum
            current_sums[current_size] = digit;
            current_size++;
            
            if(l >=2){
                int sum_val = current_sums[current_size -1];
                
                // Add all possible new sums of substrings of length >=2
                // which are all the current_sums except the last one
                // But to ensure all possible sums are tracked, iterate through all
                // Here, to simplify, check all current_sums of length >=2
                // So, iterate through last (current_size) sums and check their sums
                // Alternatively, keep separate sums
                
                // To handle all substrings of length >=2, we need to track all possible
                // substrings of length >=2 ending at current position
                // Which includes all current_sums where their corresponding lengths >=2
                // But since l increases by 1 each time, length is automatically managed
                
                // To track all possible substrings, iterate through all current_sums and
                // for those with length >=2, check their sums
                // However, this becomes O(l^2), which is too slow
                // Instead, use the fact that we are adding one digit at a time
                
                // Thus, to simplify, track all possible substring sums of length >=2
                // by considering all possible previous substrings
                
                // But to keep it efficient, use the following:
                // For each new sum, check if it's already in 'seen'
                // If any sum is duplicated, mark duplicate_found and break
                // Else, set the sum in 'seen'
                
                // Iterate through all current_sums and set them in 'seen'
                // If set bit was already set, mark duplicate
                
                // Implemented as follows:
                for(int j=0; j <current_size; ++j){
                    int sum_val2 = current_sums[j];
                    if(j <1){ // substrings of length >=2
                        if(l -j <=1){
                            continue;
                        }
                    }
                    // Now, check if the substring length >=2
                    if(l -j <2){
                        continue;
                    }
                    // Check the sum in 'seen'
                    if(sum_val2 <64){
                        if(seen0 & (1ULL << sum_val2)){
                            duplicate_found = true;
                            break;
                        }
                        seen0 |= (1ULL << sum_val2);
                    }
                    else if(sum_val2 <128){
                        int bit = sum_val2 -64;
                        if(seen1 & (1ULL << bit)){
                            duplicate_found = true;
                            break;
                        }
                        seen1 |= (1ULL << bit);
                    }
                    else{
                        int bit = sum_val2 -128;
                        if(seen2 & (1ULL << bit)){
                            duplicate_found = true;
                            break;
                        }
                        seen2 |= (1ULL << bit);
                    }
                }
                
                if(duplicate_found){
                    break;
                }
            }
            
            if(!duplicate_found){
                dp[i + l] = (dp[i + l] + dp[i]) % MOD;
            }
            else{
                break; // No longer valid to extend this substring
            }
        }
    }
    
    cout << dp[n];
}