主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始的正整數陣列 nums。
陣列 nums 的一個子集合如果其元素之乘積是一個「無平方整數」，則該子集合是「無平方的」。
一個無平方整數為一個整數，其無法被除了 1 以外的平方數整除。
回傳陣列 nums 是無平方的子集合之數量。由於答案可能太大，先將其模 10 ^ 9 + 7 後再回傳。
nums 的一個子集合為一個可以藉由從 nums 中刪除若干個元素（可以不刪，但不能刪掉全部的元素）而得到的陣列。兩個子集合是相異的，若且唯若兩者各自選擇刪除的元素之索引值是不同。
限制：
1 ≦ nums.length ≦ 1000
1 ≦ nums[i] ≦ 30
範例測資：
範例 1：
輸入： nums = [3,4,4,5]
輸出： 3
解釋： 這個例子有 3 個無平方子集合：
- 包含第 0 個元素 [3] 的子集合。其元素乘積為 3，其為一個無平方整數。
- 包含第 3 個元素 [5] 的子集合。其元素乘積為 5，其為一個無平方整數。
- 包含第 0 和 3 個元素 [3,5] 的子集合。其元素乘積為 15，其為一個無平方整數。
可以證明給定的陣列中沒有多於 3 個無平方子集合存在。
範例 2：
輸入： nums = [1]
輸出： 1
解釋： 這個例子有 1 個無平方子集合：
- 包含第 0 個元素 [1] 的子集合。其元素乘積為 1，其為一個無平方整數。
可以證明給定的陣列中沒有多於 1 個無平方子集合存在。
解題思維：
可以看到 < 30 的質數為 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 這十個。
而如果有一個數字存在著某個質因數之次方至少為 2，則代表其必不是無平方整數（因為存在至少一個平方數可以整除該數）；反之，則其必為一個無平方整數。
再加上我們可以用一個 10 位元長的二進位數字（即十進位的 0 ～ 1023）來表示一個數字的質因數分解結果（因為根據上面，我們現在每個質因數次方只能是 0 或是 1）。
因此我們能使用動態規劃（Dynamic Programming，DP）的精神來求出有多少個無平方整數子集合：
定義一個二維陣列 D，其中 D[i][j] 代表著在考慮 nums[0] ～ nums[i] 的情況下，乘積的質因數分解結果為 j 的子集合有多少個。
可看到其遞迴式為：
如果 nums[i] 為無平方整數且本身的質因數分解結果為 X，則：
D[0][X] = 1，如果 i == 0、
D[0][j] = 0，如果 i == 0 且 j != X、
D[i][j] = D[i - 1][j] + D[i - 1][0] + 1、
D[i][j] = D[i - 1][j] + D[i - 1][j ^ X]，其中 j & X == X（代表著子集合可選，也可不選 nums[i] 來使得質因數分解結果為 j）、
D[i][j] = D[i - 1][j]，其中 j & X != X（代表選了 nums[i] 之後子集合的分解結果必不為 j）。
（且「^」和「&」代表位元操作中的 XOR 和 AND）
如果 nums[i] 本身不是無平方整數，則：
D[0][j] = 0，對於任意 j 值、
D[i][j] = D[i - 1][j]，對於任意 j 值。
最後所求的子集合數量即為 D[n - 1][0] + D[n - 1][1] + …… + D[n - 1][1023]，其中 n 為 nums 的長度。記得每個操作都要模 10 ^ 9 + 7。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
