# Leetcode 解題記錄 3539. Find Sum of Array Product of Magical Sequences🏚️
### 題目大意:
給定一組int array : nums，以及int M和K
定義 seq : sequence
* seq 大小為 M (從int array可重複取M次)
* S = 2^(seq\[0\]) + 2^(seq\[1\]) + ... + 2^(seq\[M-1\])，S的二進位剛好有K個bits是1
* prod(seq) = (nums[seq[0]] * nums[seq[1]] * ... * nums[seq[m - 1]])
求所有滿足上面條件的prod(seq)的總和

### 解法思路:
題目的要求很明顯要搞組合問題，又是可重複的sequence第一直覺就是搞二項式或多項式自己乘自己，所以可以想像把nums放在生成函式f上，求f^m。再來是按照不同的S分類，最一開始就是 `[1:nums[0],2:nums[1],4:nums[2],8:nums[3],....,2^n-1:nums[n-1]]`
在觀察這些狀態轉移就是簡單的加法，所以f*f的結果可以將S相同的prod先加起來，操作會像是

   unordered_map<long long,long long> mul_states(unordered_map<long long,long long> &a,unordered_map<long long,long long> &b,int mod){
        unordered_map<long long,long long> res;
        for(auto &as:a){
            for(auto &bs:b){
                long long nxt_state = as.first+bs.first;
                res[nxt_state]=(res[nxt_state]+as.second*bs.second)%mod;
            }
        }
        return res;
    }

接下來再用fastpow的方式可以求出所有S的product在挑出set bits為K的加總

int magicalSum(int M, int K, vector<int>& nums) {
        int mod = 1e9+7,n = nums.size();
        unordered_map<long long,long long> states,pow_states;
        states[0] = 1;
        for(int i=0;i<n;i++){
            pow_states[1ll<<i] = nums[i];
        }
        int t = 1;
        while(M){
            if(M&1){
                states = mul_states(states,pow_states,mod);
            }
            if(M>1)pow_states=mul_states(pow_states,pow_states,mod);
            M>>=1;
        }
        long long ans = 0;
        for(auto &s:states){
            if(__builtin_popcountll(s.first)==K){
                ans+=s.second;
                ans%=mod;
            }
        }
        return ans;
    }

但是這樣作狀態樹會爆，想到開始懷疑人生，心態炸裂，道心已毀，放棄思考。
解法留在下面，想不出來破大房的可以往下看


<br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/>

這裡用一個方式去壓縮狀態，先前定義的狀態修改億點點就可以了。
先定義dp[i][m][k][b]
最簡單的來說如果我先把位置0的nums[0]出現的可能性都處理完那麼接下來S的最小的bit就固定了(因為之後不會再乘上nums[0]，其他的狀態要加也是2,4,8,...，不會動到最小bits)，所以這個最小bit可以用另一個dim紀錄，因為前一個i殘留的狀態最多是M/2，當前的狀態最多會是(M/2+M)/2\<M，所以狀態數是可以控制的。
* dp state中
* i 代表處理多少位置，同時也是k dim size的上限
* m 代表已經乘過幾個數字，最多是M
* k 代表處理過的bits有幾個是1
* b 有可能因為後續操作而改變的bits state
整個狀態轉移就會像是
//從狀態dp[i-1][m][k][b]，第i個元素取q次
dp[i][m+q][k+((b+q)&1)][(b+q)>>1] += dp[i-1][m][k][b]*(...);
(...) : inverse of q! under modulo 1e9+7 (排列組合先除，之後一起乘n!)

最後在挑出dp[n-1][K]中符合的部分加起來，乘上n! (mod 1e9+7)
簡單舉個幾個例子:

    seq = [1,2,1,3], S = 16
    用dp的方式則會記錄在下面的路徑中
    dp[0][0][0][0] -> dp[0][2][0][1] -> dp[1][3][0][1] -> dp[2][4][0][1]
    S =     0      ->        4       ->        8       ->        16      
    
    seq = [1,0,2,2], S = 11
    dp[0][1][1][0] -> dp[0][2][2][0] -> dp[1][4][2][1] -> dp[2][4][3][0]
    S =     1      ->        3       ->        11      ->        11      
    

### Murmur
解了不少hard problem，大部分想一下都可以解，要看hint的也不到十題，這題是第一題我看hint還看不懂到去看解答的，整個大破房，一開始的方向錯了彎不過來，so sad。