正題

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

---

題目大意

一個(gè)長(zhǎng)度為$n$的棋盤上放下$k$個(gè)棋子。

第一個(gè)要是白色，下一個(gè)要是黑色，在下一個(gè)是白色以此類推。

先手操控白，后手操控黑。白色只能往右，黑色只能往左。每次操作的可以移動(dòng)$d$個(gè)棋子任意步。

求先手必勝的初始狀態(tài)數(shù)

$1\le d\le k\le n\le 10^4,1\le k\le 100$且$k$為偶數(shù)

---

解題思路

把兩個(gè)黑白棋子之間的長(zhǎng)度看為石頭堆就是一個(gè)$Ni{m}_k$游戲了。

$Ni{m}_k$游戲的結(jié)論就是$k+1$進(jìn)制下各個(gè)位置的$1$的個(gè)數(shù)$\%(k+1)$等于$0$的話先手必?cái)　?/p>

因?yàn)橄仁直貏俦容^麻煩，考慮減去先手必?cái)〉那闆r

這個(gè)東西和昨天的一道$ARC$的題目很像，每個(gè)位分開考慮，設(shè)$f_{i,j}$表示前$i$個(gè)位都是$0$時(shí)，用了$j$個(gè)石頭的方案。

那么轉(zhuǎn)移也十分顯然，枚舉一個(gè)選的倍數(shù)$i$然后分配到$\frac{k}{2}$個(gè)石頭堆中，方案數(shù)就是$\left(\genfrac{}{}{0ex}{}{\frac{k}{2}}{i\times (d+1)}\right)$。

然后統(tǒng)計(jì)答案的時(shí)候?qū)τ谑雍蜑?span id="ze8trgl8bvbq" class="katex--inline">$i$的貢獻(xiàn)就是$\left(\genfrac{}{}{0ex}{}{n?\frac{k}{2}?i}{\frac{k}{2}}\right)$（因?yàn)槊恳欢训膫€(gè)數(shù)固定，所以選擇起點(diǎn)就好了）

時(shí)間復(fù)雜度$O(nk\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e4+10,M=110,P=1e9+7; ll n,k,d,ans,C[N][M],f[16][N]; signed main() {scanf("%lld%lld%lld",&n,&k,&d);C[0][0]=1;n-=k;k/=2;d++;for(ll i=1;i<N;i++)for(ll j=0;j<M;j++)C[i][j]=((j?C[i-1][j-1]:0)+C[i-1][j])%P;ll z=0;ans=C[n+2*k][k*2];f[0][0]=1;for(ll p=1;p<=n;p<<=1){z++;for(ll j=0;j<=n;j++)for(ll i=0;j+i*p*d<=n&&i*d<=k;i++)(f[z][j+i*p*d]+=f[z-1][j]*C[k][i*d]%P)%=P;}for(ll i=0;i<=n;i++)(ans+=P-f[z][i]*C[n+k-i][k]%P)%=P;printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P2490-[SDOI2011]黑白棋【博弈论,dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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