# Leetcode 解題記錄 3343. Count Number of Balanced Permutations
### 題目大意:
給定一個由數字組成字串(可以是0開頭) : num
將num重新排列，有多少排列方式是奇數位的總和與偶數為總和相等?

### 解法思路:
這題聞起來就很像上次讓我破大房的[題目](https://hackmd.io/bND5dxEMQyuDDbBMU3-Lng)，幾乎有87%像
先統計每種數字有幾個:
`cnt = [0:10, 1:3, 2:4, ..., 9:3] // 10個'0',3個'1',4個2,....,3個9`
dp會長這樣:
`dp[i][m][sum]``:
* i :當前處理的數字,i in `[0,1,2,3,4,5,6,7,8,9]`
* m :當前狀態偶數位有幾個數字
* sum :當前狀態偶數位數字和
轉移函數會是:
* p :偶數位增加p個'i'

    dp[i][m+p][s+p*i] += dp[i-1][m][s]/(p!*(cnt[i]-p)!);

最後在結果在乘上`(n/2)!*(n-n/2)!`
以上都要做`modulo 1e9+7`

### Murmur
看完這題才恍然大悟，如果寫過這題也許那破房題是有機會解出來的(這題的題號比較早)，雖然說那題的狀態壓縮真的很鬼...