1009
这么能猜?
这个数据范围,对博弈论来说肯定存在某种结论。故这题是结论题。
设\(dp[n]\)表现有\(n\)个物体时敌方先手，我的胜率。则敌方先手后轮到我时有n-1或者n-4个物体，我再取物体。我取物体时肯定要的是胜率最大，以是有转移方程\(dp[n]=\frac{1}{2}*max(dp[n-1-1],dp[n-1-4])+\frac{1}{2}*max(dp[n-4-1],dp[n-4-4]))=\frac{max(dp[n-2],dp[n-5])+max(dp[n-5],dp[n-8])}{2}\)。数组越界时说明不存在这种选取方案。可以根据这个递推式打表或者手搓20以内的结果，就能发现规律。
赛时还是不够冷静啊!!!,可惜了，代码如下：
[code]const int mod=998244353;int ksm(int x,int y){ int ans=1,base=x; while(y){ if(y&1){ ans*=base; ans%=mod; } base*=base; base%=mod; y>>=1; } return ans%mod;}int inv(int x){ return ksm(x,mod-2)%mod;}void solve(){ int n; cin>>n; int m=n%5,a,b;//a分母,b分子 if(m==2||m==0){ cout |
