正題

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

---

題目大意

$1\times n$的網格上有$m$個硬幣，兩個人輪流向前移動一個硬幣但是不能超過前一個硬幣，無法移動者輸。
求有多少種情況先手必勝。

---

解題思路

竟然有我會的題，我感動

位置做差分再減去$1$之后就是一個經典的階梯博弈問題了，結論就是奇數位置的異或和。

但是這題是計數，先讓$n$減去$m$，然后正難則反考慮求總方案和后手必勝的情況，這樣問題就變為有多少個長度為$m$的非負整數序列滿足它們的和不超過$n$且奇數位置的異或和為$0$。

考慮枚舉奇數位置的和，奇數位置個數為$z=?\frac{m+1}{2}?$，設$f_i$表示$z$個數的和為$i$時異或和為$0$的方案數，這個狀態直接計算起來很難搞。

可以枚舉每一個位的$1$的數量，顯然每一個位的$1$數量肯是偶數。然后用組合數轉移即可。

然后設$g_i$表示$m?z$個數和不超過$i$的方案數，那么有$g_i={\sum }_{j=0}^i\left(\genfrac{}{}{0ex}{}{j+m?z?1}{m?z?1}\right)$，前綴和轉移就好了。

然后答案就是$\left(\genfrac{}{}{0ex}{}{n+m}{m}\right)?{\sum }_{i=0}^n{f}_i{g}_{n?i}$（注意這里的$n$已經減去$m$了），因為模數不是質數直接楊輝三角求就好了。

時間復雜度$O(nm\log m)$，當然肯定是跑不滿的

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2e5,P=1e9+9; ll n,m,ans,c[N][51],f[N],g[N]; signed main() {scanf("%lld%lld",&n,&m);ans=0;if(n<=m)return puts("0")&0;c[0][0]=1;for(ll i=1;i<=n;i++)for(ll j=0;j<=min(i,m);j++)c[i][j]=((j?c[i-1][j-1]:0)+c[i-1][j])%P;n-=m;ll z=(m+1)/2;f[0]=1;for(ll i=1;i<=18;i++)for(ll j=n;j>=0;j--)for(ll k=1;k<=z/2;k++){if(j<(k*(1<<i)))break;(f[j]+=f[j-k*(1<<i)]*c[z][2*k]%P)%=P;}for(ll i=0;i<=n;i++)g[i]=(g[i-1]+c[i+m-z-1][m-z-1])%P;for(ll i=0;i<=n;i++)(ans+=f[i]*g[n-i]%P)%=P;printf("%lld\n",(c[n+m][m]-ans+P)%P);return 0; }

總結

以上是生活随笔為你收集整理的P5363-[SDOI2019]移动金币【阶梯博弈,dp,组合数学】的全部內容，希望文章能夠幫你解決所遇到的問題。

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