2025春季钉耙编程5补题

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以内的结果，就能发现规律。
  赛时还是不够冷静啊!!!,可惜了，代码如下：

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<<1<<endl;
		return;
	}else if(m==1){
		if(n==1) a=2,b=1;
		else a=ksm(2,n/5),b=a-1;
	}else if(m==3){
		if(n==3) a=4,b=3;
		else a=ksm(2,ceil(n/5.0)+1),b=a-1;
	}else if(m==4){
		if(n==4) a=2,b=1;
		else a=ksm(2,ceil(n/5.0)),b=a-1;
	}
	cout<<(b%mod*inv(a)%mod)%mod<<endl;
}

原文链接：2025春季钉耙编程5补题