Untitled conversation
- User
[APC001] E - Linear Map
题目背景
请注意本题的特殊时间限制,并酌情使用较快的输入输出方式。
在广阔的 florr 世界中,有一个不为人知的角落,它的建立是为了方便快速测试新 mob,而现在它被废弃了,但没有消失。
冒险者 MF 找到了这里,并发现其名字为:Linear map。
题目描述
Linear map 可看作一个字符串,每个字符都是一个 的数字。
MF 认为,如果一个字符串存在两段长度均 的不同区间的和相同,那么该字符串是无趣的。
比如, 就是无趣的字符串,因为 ,而 也是无趣的字符串,因为 。相反, 和 都不是无趣的字符串。
MF 打算将 Linear map 划分为若干非空连续且不重复的子段,这些子段包含了整个字符串的所有字符,且满足每个子段都不是无趣的字符串。
MF 是一个有趣的人,于是它想算出划分的方案数,并对 取模。
输入格式
一行一个字符串 。
输出格式
一行一个整数表示答案对 取模后的结果。
样例 #1
样例输入 #1
453样例输出 #1
4样例 #2
样例输入 #2
3333样例输出 #2
5样例 #3
样例输入 #3
9475739582850286样例输出 #3
9360提示
样例解释
- 样例
所有划分均合法:。
- 样例
合法方案为:。
数据范围
对于 的数据,满足 ,且 中仅包含数字。
- Assistant
To solve the problem of partitioning the given string into non-empty, contiguous, and non-overlapping substrings where each substring is "interesting" (i.e., it does not contain two different intervals of length greater than 1 with the same sum), we can employ a Dynamic Programming (DP) approach combined with efficient window management to handle the large input size effectively.
Overview
-
Dynamic Programming Setup:
- DP Array (
dp):dp[i]represents the number of valid ways to partition the firsticharacters of the string. - Cumulative Sum Array (
cumulative_sum): To efficiently compute the sum ofdp[j]for ranges, maintain a cumulative sum array wherecumulative_sum[i] = dp[0] + dp[1] + ... + dp[i].
- DP Array (
-
Sliding Window Technique:
- Window Boundaries (
leftandright): Maintain a sliding window[left, right)where all substring sums within this window are unique. - Hash Map (
last_seen_sum): Keep track of the last index where each sum of substrings of length ≥2 was seen. This helps in adjusting theleftboundary when a duplicate sum is detected.
- Window Boundaries (
Step-by-Step Solution
-
Initialization:
- Set
dp[0] = 1as the base case (empty string). - Initialize
cumulative_sum[0] = 1. - Initialize
left = 0. - Initialize an empty hash map
last_seen_sumto keep track of sums of substrings.
- Set
-
Iterate Through the String:
- For each position
ifrom1ton(length of the string):- Update Substring Sums:
- For each ongoing substring ending at position
i-1, calculate the new sum by adding the current digits[i-1]. - Additionally, consider the new substring starting at position
i-1of length2.
- For each ongoing substring ending at position
- Check for Duplicate Sums:
- For each newly calculated sum:
- If the sum has been seen before (i.e., exists in
last_seen_sumandlast_seen_sum[s_sum] ≥ left):- Update
lefttolast_seen_sum[s_sum] + 1to exclude the previous occurrence and maintain the uniqueness constraint.
- Update
- Update
last_seen_sum[s_sum] = i - 1to record the latest index where this sum was seen.
- If the sum has been seen before (i.e., exists in
- For each newly calculated sum:
- Update DP Array:
dp[i] = (cumulative_sum[i-1] - cumulative_sum[left-1]) % 998244353
- Update Cumulative Sum:
cumulative_sum[i] = (cumulative_sum[i-1] + dp[i]) % 998244353
- Update Substring Sums:
- For each position
-
Final Answer:
- The total number of valid partitions is
dp[n]modulo998244353.
- The total number of valid partitions is
Optimization Considerations
-
Efficient Sum Tracking: Given the large input size (
|s| ≤ 1.5 × 10^7), it's crucial to handle substring sums efficiently. This can be achieved by:- Limiting the number of ongoing substrings by leveraging the small range of digit values (
0-9), ensuring that the number of unique sums at any point remains manageable. - Using an array instead of a hash map for
last_seen_sumif the range of possible sums is within feasible memory limits.
- Limiting the number of ongoing substrings by leveraging the small range of digit values (
-
Space Optimization:
- Since
ncan be up to1.5 × 10^7, it's essential to manage memory usage carefully. Utilize arrays with appropriate data types to storedpandcumulative_sum.
- Since
-
Time Optimization:
- By using the cumulative sum array, the DP transition step becomes an O(1) operation, ensuring the overall time complexity remains linear (O(n)).
Example Walkthrough
Sample Input 1:
453- Possible Partitions:
{"453"}{"45","3"}{"4","53"}{"4","5","3"}
All partitions are valid as none contain "uninteresting" substrings. Thus, the output is
4.Sample Input 2:
3333- Valid Partitions:
{"33","33"}{"33","3","3"}{"3","33","3"}{"3","3","33"}{"3","3","3","3"}
Partitions like
{"333","3"}or{"4","5","3"}are invalid as they contain "uninteresting" substrings (e.g., multiple "33" with the same sum). Thus, the output is5.Final Thoughts
The key to solving this problem efficiently lies in:
- Dynamic Programming to keep track of valid partitions.
- Sliding Window Technique to ensure that all substring sums within a window are unique.
- Efficient Data Structures to manage and query substring sums quickly.
Implementing this approach with careful attention to optimization will ensure that the solution works within the stringent time and memory constraints.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.