傳統(tǒng)游戲

• 看到題，第一想法是設$dp[k][s]$表示選了$k$個數(shù)，當前異或和為$s$的方案數(shù)，但這樣產(chǎn)生一個問題：要如何保證所選的數(shù)不重復且無序呢？
• 一種方法是修改狀態(tài)：我們增設一維$i$，$dp[i][k][s]$表示從$\le i$的范圍中 (引入“階段”使決策有序化) 選了$k$個數(shù)，當前異或和為$s$的方案數(shù)。(按任意順序選數(shù)難以得知哪些數(shù)被選過，但如果強制按從小到大的順序選數(shù)，便可保證所選的數(shù)不重且無序。思路類似背包的狀態(tài)設計。)
  這樣可以過掉$subtask1$
• 上面的方法適合$n$大$L$小的情況，然而此題中$n$遠小于$L$。我們轉(zhuǎn)化一下思路，從高往低考慮二進制下的每一位，枚舉$n$個所選數(shù)的這一位上是0還是1，每一位只有$2^n$種情況，總時間復雜度$O(2^{n}L)$：設$F[i][lim][sta]$表示做完了從高往低的前$i$位，最大的那個數(shù)是否還等于$m$ ，從大往小每個數(shù)是否等于下一個數(shù)(狀壓) 的方案數(shù)，數(shù)位DP即可
• 另一種思路是：直接計算不重且無序的方案數(shù)不方便，因此先算可重且有序的方案數(shù)，再通過容斥搞出不重且無序的方案數(shù)。(思路類似簡單的博弈題)
• 考慮如何計算可重且有序的方案數(shù)：
• 類似 數(shù)位DP 的做法，從高位往低位考慮，假設當前做到第$i$位。
  不難發(fā)現(xiàn)，如果一個數(shù)的前$i?1$位還等于$m$的前$i?1$位 ，那么接下來的一位填什么還會受限制；
  然而如果一個數(shù)的前$i?1$位已經(jīng)小于$m$的前$i?1$位了，那么接下來所有位填什么都不會受限制。
• 這樣一來，如果做完第$i$位后，這$n$個數(shù)中有某個數(shù)的前$i$位小于$m$的前$i$位，那么可以讓其余$n?1$個數(shù)在填第$i+1$位以及之后的位時，不再考慮異或和為0的限制，然后用這個數(shù)把最終的異或和調(diào)整為0。
• 因此，我們可以枚舉從哪一位開始出現(xiàn)確定小于$m$的數(shù)，然后計算方案數(shù)。
  不妨設在這一位填1后后面幾位還有$a$種方案(僅考慮$<m$的限制)，填0后還有$b$種方案(僅考慮$<m$的限制)，那么方案數(shù)為：$$\sum _{i=0}^{n?1}{C}_n^i{a}^i{b}^{n?1?i}[imod2=0]$$(若某個數(shù)在這一位確定小于$m$，那么此數(shù)的這一位必為0，其余$n?1$個數(shù)仍要保證在這一位上的異或和為0，$i$表示在這一位填1的數(shù)的個數(shù))
• 如此，我們可以在$O(nL)$的時間內(nèi)算出選$n$個數(shù)的可重且有序的方案數(shù)。但因為要做容斥，所以我們需要知道所有選$1$~$n$個數(shù)的方案數(shù)，這樣復雜度就是$O(n^{2}L)$了。
• 仔細觀察，發(fā)現(xiàn)式子還能繼續(xù)化簡：
  ${\sum }_{i=0}^{n?1}{C}_n^i{a}^i{b}^{n?1?i}[imod2=0]$
  $={\sum }_{i=0}^n{C}_n^i{a}^i{b}^{n?i}[imod2=0]?a^n[nmod2=0]$
  $=\frac{{\sum }_{i=0}^n{C}_n^i{a}^i{b}^{n?i}+{\sum }_{i=0}^n{C}_n^i(?a{)}^i{b}^{n?i}}{2}?a^n[nmod2=0]$
  $=\frac{(a+b{)}^n+(b?a{)}^n}{2}?a^n[nmod2=0]$
  這樣，時間復雜度就是$O(nL)了$
• 考慮如何用容斥得出答案：

總結(jié)

以上是生活随笔為你收集整理的[XSY] 传统游戏（DP、容斥）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。