太原做网站哪家公司好,网上商城平台开发,百度搜索推广和信息流推广,自己做的网站为什么访问不正题
题目链接:https://ac.nowcoder.com/acm/contest/1104/A 题目大意
一个010101序列#xff0c;如果首项是000#xff0c;那么你就可以变111或者不变。如果是111那么对方可以选择变000或者不变#xff0c;如果全变成0那么你获胜#xff0c;如果永远不能全变成0那么对手…正题
题目链接:https://ac.nowcoder.com/acm/contest/1104/A 题目大意
一个010101序列如果首项是000那么你就可以变111或者不变。如果是111那么对方可以选择变000或者不变如果全变成0那么你获胜如果永远不能全变成0那么对手获胜。
求在双方都采取最有策略的情况下有多少个长度为nnn的序列可以使你获胜。 解题思路
我们考虑一下自己能够做什么可以将一段连续的1变成0也就是可以将两段连续的1连接起来。对手可以将一段连续的1变成0改变后那么就可以变成一段更长的连续的1那么下次你就可以再次全部变成0。
那么结论就是任何序列你都可以获胜所以答案就是2n2^n2n快速幂即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll XJQ998244353;
ll n;
ll power(ll x,ll b)
{ll ans1;while(b){if(b1) ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
int main()
{scanf(%lld,n);printf(%lld,power(2,n));
}
