題目：給定數字字符串（長度 ≤100），可任意排列。求有多少種排列形成的數能被 11 整除。結果模 10⁹+7。數字可重複，排列視為不同（即使數字相同，位置不同視為不同排列）。
10 ≡ -1 (mod 11) ⇒ 10ᵏ ≡ (-1)ᵏ (mod 11)。
數字 dₖ...d₁d₀ 模 11 等價於 Σ (-1)ᵏ dₖ。即 奇數位和 - 偶數位和 ≡ 0 (mod 11)。
設總長 n，奇數位個數 odd = (n+1)/2，偶數位 even = n/2。
問題轉化為：從多重集合中選 odd 個數字放奇數位，其餘放偶數位，使 (sum_odd - sum_even) % 11 == 0。
dp[i][j][k]：處理完數字 0..i-1，已放入奇數位 j 個數字，(奇數位和 - 偶數位和) % 11 = k 的方案數。
i ∈ [0,10]，j ∈ [0, odd]，k ∈ [0,10]。
設數字 i 出現 cnt 次。枚舉放入奇數位 x ∈ [0, min(cnt, odd-j)]，偶數位放 cnt-x。
貢獻差值：delta = (x - (cnt-x)) * i = (2x - cnt) * i。
組合數：選奇數位置 C(odd-j, x)，選偶數位置 C(even-(processed-x), cnt-x)。
轉移：
dp[i+1][j+x][(k+delta)%11] += dp[i][j][k] * C(odd-j, x) * C(even-(tot-j), cnt-x)
其中 tot 為已處理總數字數。
總方案含前導零情況。若數字 0 存在，強制最高位（奇數位第 1 位）不為 0：
先減去 1 個 0，對長度 n-1 跑相同 DP 得 ans2。
答案 = (ans1 - ans2) % MOD。
const int MOD = 1e9+7;
long long C[105][105];
long long dp[11][105][11];
int digitCnt[10];
void initComb() {
for (int i = 0; i <= 100; ++i) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j)
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
long long solve(int len) {
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1;
int odd = (len + 1) / 2;
int processed = 0;
for (int d = 0; d <= 9; ++d) {
int cnt = digitCnt[d];
for (int j = 0; j <= odd && j <= processed; ++j) {
for (int x = 0; x <= cnt && j+x <= odd; ++x) {
int delta = ((2*x - cnt) * d) % 11;
if (delta < 0) delta += 11;
long long ways = C[odd - j][x] * C[len - processed - (odd - j)][cnt - x] % MOD;
for (int k = 0; k < 11; ++k) {
int nk = (k + delta) % 11;
dp[d+1][j+x][nk] = (dp[d+1][j+x][nk] + dp[d][j][k] * ways) % MOD;
}
}
}
processed += cnt;
}
return dp[10][odd][0];
}
int main() {
initComb();
string s;
while (cin >> s) {
memset(digitCnt, 0, sizeof(digitCnt));
for (char c : s) digitCnt[c-'0']++;
long long ans1 = solve(s.size());
long long ans2 = 0;
if (digitCnt[0] > 0) {
digitCnt[0]--;
ans2 = solve(s.size() - 1);
digitCnt[0]++;
}
cout << (ans1 - ans2 + MOD) % MOD << '\n';
}
return 0;
}
C[n][k] 用於計算位置選擇方案數。| 指標 | 複雜度 | 說明 |
|---|---|---|
| 時間 | O(10 · odd · 11 · maxCnt) | ~幾萬次操作，極快 |
| 空間 | O(10 · odd · 11) | DP 表 |
LA 6529 是「數位 DP + 組合數學 + 同餘理論」的綜合題。它巧妙利用 11 的整除規則將排列計數問題降維為子集選擇問題，再用 DP 統計方案數。此模式可推廣至其他模數（如 3, 9, 7, 13 等）的類似問題，核心在於找到「位置權重模數週期性」並構造相應 DP 狀態。
