HDU 4632 Palindrome subsequence：區間 DP + 容斥原理計數回文子序列

題目大意

給定長度 ≤1000 的小寫字母字符串 S，統計所有非空回文子序列的個數（位置不同視為不同子序列），答案模 10007。T ≤ 50 組測試。

區間 DP 定義

dp[i][j]：區間 [i, j] 內的回文子序列個數（1-based，i≤j）。

轉移方程推導

考慮區間 [i, j] 的最外層字符 S[i], S[j]：

• 若 S[i] == S[j]：新增回文 = 以 S[i]、S[j] 為兩端的回文，數量為 dp[i+1][j-1] + 1（+1 為雙字符回文 S[i]S[j]）。
• 無論是否相等，包含在 [i+1, j] 和 [i, j-1] 中的回文都包含在 [i, j] 中，但 [i+1, j-1] 被重複計算了兩次，需減去（容斥原理）。

綜合：
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
若 S[i]==S[j]：dp[i][j] += dp[i+1][j-1] + 1
化簡得：
S[i]==S[j] → dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1
S[i]!=S[j] → dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]

計算順序

按區間長度從 1 到 n 遞增，或按 i 從 n 遞減到 1，j 從 i 遞增到 n。

模運算注意

減法可能產生負數，用 (x%MOD+MOD)%MOD 或 (x+5*MOD)%MOD 保證非負。

參考代碼（C++）