正題

題目鏈接:https://ac.nowcoder.com/acm/contest/1104/A

---

題目大意

一個$01$序列，如果首項是$0$，那么你就可以變$1$或者不變。如果是$1$那么對方可以選擇變$0$或者不變，如果全變成0那么你獲勝，如果永遠不能全變成0那么對手獲勝。

求在雙方都采取最有策略的情況下有多少個長度為$n$的序列可以使你獲勝。

---

解題思路

我們考慮一下自己能夠做什么，可以將一段連續的1變成0，也就是可以將兩段連續的1連接起來。對手可以將一段連續的1變成0，改變后那么就可以變成一段更長的連續的1，那么下次你就可以再次全部變成0。

那么結論就是任何序列你都可以獲勝，所以答案就是$2^n$，快速冪即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll XJQ=998244353; ll n; ll power(ll x,ll b) {ll ans=1;while(b){if(b&1) ans=ans*x%XJQ;x=x*x%XJQ;b>>=1;}return ans; } int main() {scanf("%lld",&n);printf("%lld",power(2,n)); }

總結

以上是生活随笔為你收集整理的牛客-无形的博弈【结论题,快速幂】的全部內容，希望文章能夠幫你解決所遇到的問題。

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