Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

Untitled conversation

  1. User

    [APC001] E - Linear Map

    题目背景

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

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

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

    题目描述

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

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

    比如,34213421 就是无趣的字符串,因为 3+4=4+2+13+4=4+2+1,而 50235023 也是无趣的字符串,因为 5+0=2+35+0=2+3。相反,1313 和 285285 都不是无趣的字符串。

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

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

    输入格式

    一行一个字符串 ss。

    输出格式

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

    样例 #1

    样例输入 #1

    453
    

    样例输出 #1

    4
    

    样例 #2

    样例输入 #2

    3333
    

    样例输出 #2

    5
    

    样例 #3

    样例输入 #3

    9475739582850286
    

    样例输出 #3

    9360
    

    提示

    样例解释

    • 样例 #1\tt\#1

    所有划分均合法:{453},{45,3},{4,53},{4,5,3}\{453\},\{45,3\},\{4,53\},\{4,5,3\}。

    • 样例 #2\tt\#2

    合法方案为:{33,33},{33,3,3},{3,33,3},{3,3,33},{3,3,3,3}\{33,33\},\{33,3,3\},\{3,33,3\},\{3,3,33\},\{3,3,3,3\}。

    数据范围

    对于 100%100\% 的数据,满足 1≤∣s∣≤1.5×1071\le |s|\le 1.5\times 10^7,且 ss 中仅包含数字。

  2. 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

    1. Dynamic Programming Setup:

      • DP Array (dp): dp[i] represents the number of valid ways to partition the first i characters of the string.
      • Cumulative Sum Array (cumulative_sum): To efficiently compute the sum of dp[j] for ranges, maintain a cumulative sum array where cumulative_sum[i] = dp[0] + dp[1] + ... + dp[i].
    2. Sliding Window Technique:

      • Window Boundaries (left and right): 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 the left boundary when a duplicate sum is detected.

    Step-by-Step Solution

    1. Initialization:

      • Set dp[0] = 1 as the base case (empty string).
      • Initialize cumulative_sum[0] = 1.
      • Initialize left = 0.
      • Initialize an empty hash map last_seen_sum to keep track of sums of substrings.
    2. Iterate Through the String:

      • For each position i from 1 to n (length of the string):
        • Update Substring Sums:
          • For each ongoing substring ending at position i-1, calculate the new sum by adding the current digit s[i-1].
          • Additionally, consider the new substring starting at position i-1 of length 2.
        • Check for Duplicate Sums:
          • For each newly calculated sum:
            • If the sum has been seen before (i.e., exists in last_seen_sum and last_seen_sum[s_sum] ≥ left):
              • Update left to last_seen_sum[s_sum] + 1 to exclude the previous occurrence and maintain the uniqueness constraint.
            • Update last_seen_sum[s_sum] = i - 1 to record the latest index where this sum was seen.
        • 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
    3. Final Answer:

      • The total number of valid partitions is dp[n] modulo 998244353.

    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_sum if the range of possible sums is within feasible memory limits.
    • Space Optimization:

      • Since n can be up to 1.5 × 10^7, it's essential to manage memory usage carefully. Utilize arrays with appropriate data types to store dp and cumulative_sum.
    • 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 is 5.

    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.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.