正題

題目鏈接:https://www.luogu.com.cn/problem/P5675

---

題目大意

$n$堆石子，第$i$堆有$a_i$個。指定一些石子堆使得先手必勝并指定一個先手第一個取的位置使得先手必敗，求有多少方案數。

---

解題思路

根據$NIM$游戲，只要石子數異或和為$0$則先手必敗。

然后我們考慮枚舉指定先手先去哪一堆石頭，我們要選擇一些石子堆使沒有任何一種方法取走一些石頭使得先手必敗。

我們用$f_{i,j}$表示在不包括枚舉的石頭堆的情況下，前$i$堆石頭有多少種選擇方案使得其異或和為$j$。然后若強制先手選擇第$k$堆石頭那么方案數就是$$\sum _{i=a_k}^{\infty }{f}_{n,i}$$

時間復雜度$O(n^3)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=210,XJQ=1e9+7; int n,a[N],f[N][256],ans; int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int k=1;k<=n;k++){f[0][0]=1;for(int i=1;i<=n;i++){if(i==k){for(int j=0;j<256;j++)f[i][j]=f[i-1][j]; }else{for(int j=0;j<256;j++)f[i][j]=(f[i-1][j]+f[i-1][j^a[i]])%XJQ;}}for(int i=a[k];i<256;i++)ans=(ans+f[n][i])%XJQ;}printf("%d",ans); }

總結

以上是生活随笔為你收集整理的P5675-[GZOI2017]取石子游戏【博弈论,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。