CSU 1354 Distinct Subsequences：數字子序列和的 DP 計數與去重

• 新子序列：單獨 x（若 x>0），以及在所有現有子序列後附加 x。
• newSum = (Σ dp[d]) * 10 + (Σ cnt[d] + (x>0?1:0)) * x。
• newCnt = Σ cnt[d] + (x>0?1:0)。
• 更新 dp[x] = newSum, cnt[x] = newCnt（覆蓋，因同尾數字只保留最新狀態，自動去重）。

Java 代碼

import java.util.*;
public class Main {
    static final int MOD = 1000000007;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while (T-- > 0) {
            String s = in.next();
            long[] dp = new long[10], cnt = new long[10];
            for (char ch : s.toCharArray()) {
                int x = ch - '0';
                long sum = 0, c = 0;
                for (int d = 0; d < 10; ++d) {
                    sum = (sum + dp[d]) % MOD;
                    c = (c + cnt[d]) % MOD;
                }
                if (x > 0) c = (c + 1) % MOD;
                dp[x] = (sum * 10 + c * x) % MOD;
                cnt[x] = c;
            }
            long ans = 0;
            for (int d = 0; d < 10; ++d) ans = (ans + dp[d]) % MOD;
            System.out.println(ans);
        }
    }
}

關鍵洞察

• 只保留每個尾數字的最新狀態：因子序列按位置順序構建，後出現的相同尾數字子序列集合包含前者（可通過跳過中間字符得到），故直接覆蓋即可去重。
• 前導零處理：x=0 時不新增單獨子序列（c+1），但可附加在現有子序列後。
• 公式推導：附加數字 x 相當於原值 ×10 + x，故和變為 sum*10 + cnt*x。

複雜度

• 時間：O(n × 10) = O(n)，n ≤ 10⁵ 極快。
• 空間：O(1) 兩個長度 10 數組。

總結

CSU 1354 是「子序列計數去重 + 數值和」的精妙 DP。核心技巧：按尾數字分組狀態 + 覆蓋更新實現去重 + 線性遞推公式。同類思想適用於「不同子序列個數」、「子序列和」等變體問題。