怎么SDOI2011和SDOI2019的兩道題這么像啊。。(雖然并不完全一樣)

題目鏈接: (bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=2281

(luogu) https://www.luogu.org/problemnew/show/P2490

題解: 博弈論好難啊完全學(xué)不來QAQ

題目里應(yīng)該有個限制，是先手不能左移，后手不能右移。

簡單轉(zhuǎn)化一發(fā)，就相當(dāng)于有\(n\)堆石子，每次從\(1\)到\(d\)堆中取走任意多個，最后取完的人輸。

其實這就是個Nim博弈套Bash博弈。

然后……然后我就不會了。

按理說……\(d=1\)的時候異或和為\(0\), 也就是每個二進(jìn)制位\(1\)的個數(shù)為偶數(shù)，那么這個不是連猜都能猜出來每個二進(jìn)制位\(1\)的個數(shù)為\((d+1)\)的倍數(shù)嗎……Nim博弈套Bash博弈啊……

然后感性理解一下(可能也能算個證明吧): 考慮\(d=1\) Nim游戲的正確性，顯然異或和為\(0\)時先手能且僅能將其變?yōu)椴粸?span id="ze8trgl8bvbq" class="math inline">\(0\)，而后手在這之后能將其變?yōu)闉?span id="ze8trgl8bvbq" class="math inline">\(0\). 假設(shè)先手動的最高位為\(i\), 則后手動第\(i\)位上為\(1\)的另一個石子，下面的變成與之對應(yīng)的即可。歸納可證。那么考慮\(d>1\), 當(dāng)所有數(shù)出現(xiàn)次數(shù)均為\((d+1)\)的倍數(shù)時，先手不可能依然變?yōu)槌霈F(xiàn)次數(shù)均為\((d+1)\)的倍數(shù)；從高到低考慮位\(j\), 設(shè)現(xiàn)在已經(jīng)改變的堆數(shù)為\(t\),\(t\)個數(shù)中有\(a\)個在位\(j\)上為\(1\), \(b\)個為\(0\), 并假設(shè)后手改動前這一位上\(1\)的個數(shù)模\((d+1)\)總共是\(x\). 若\(a\ge x\), 則改變這\(a\)個中的\(x\)個即可；若\(b\ge d+1-x\)則可以把\(b\)個中的\((d+1-x)\)個從\(0\)變成\(1\); 否則另外選擇\(t\)堆之外的\((x-a)\)堆變成\(1\), 則選的總數(shù)為\((x-a)+a+b=x+b\le d+1-b+b=d+1\), 故移動依然合法。(怎么寫著寫著就變成抄別的題解了……)

然后問題轉(zhuǎn)化為求\(m\)個數(shù)和為\(n\)二進(jìn)制每一位\(1\)的個數(shù)都為\((d+1)\)的倍數(shù)的方案數(shù)。(計數(shù)我也不會啊嗚嗚嗚……)

設(shè)\(dp[i][j]\)表示考慮二進(jìn)制低\(i\)位，和為\(j\)的方案數(shù)，隨便枚舉一下轉(zhuǎn)移即可

時間復(fù)雜度很低。

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #define llong long long using namespace std;inline int read() {int x=0; bool f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }const int P = 1e9+7; const int N = 2e4; const int LGN = 14; llong fact[N+3],finv[N+3]; llong dp[LGN+3][N+3]; int n,m,d;llong quickpow(llong x,llong y) {llong cur = x,ret = 1ll;for(int i=0; y; i++){if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}cur = cur*cur%P;}return ret; } llong comb(llong x,llong y) {return x<0||y<0||x<y ? 0ll : fact[x]*finv[y]%P*finv[x-y]%P;}int main() {fact[0] = 1ll; for(int i=1; i<=N; i++) fact[i] = fact[i-1]*i%P;finv[N] = quickpow(fact[N],P-2); for(int i=N-1; i>=0; i--) finv[i] = finv[i+1]*(i+1)%P;scanf("%d%d%d",&n,&m,&d); n-=m; m>>=1;for(int i=0; i*(d+1)<=m && i*(d+1)<=n; i++){dp[0][i*(d+1)] = comb(m,(d+1)*i);}for(int i=1; i<=LGN; i++){for(int j=0; j<=n; j++){llong cur = dp[i-1][j];if(cur){for(int k=0; j+(d+1)*k*(1<<i)<=n && (d+1)*k<=m; k++){llong tmp = cur*comb(m,(d+1)*k);dp[i][j+(d+1)*k*(1<<i)] = (dp[i][j+(d+1)*k*(1<<i)]+tmp)%P;}}}}llong ans = 0ll;for(int i=0; i<=n; i++){llong tmp = comb(n+m-i,m)*dp[LGN][i];ans = (ans+tmp)%P;}ans = (comb(n+m+m,m+m)-ans+P)%P;printf("%lld\n",ans);return 0; } 與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2281 Luogu P2490 [SDOI2011]黑白棋 (博弈论、DP计数)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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