EOJ Monthly 2021.9 Sponsored by TuSimple A&D

• A.Amazing Discovery
• D. Divide and Merge

A.Amazing Discovery

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int N = 2;
const ll mod = 998244353;

ll a,b,n;
struct node{
	ll m[2][2];
}res,ans;

node mul(node a,node b){
	node tmp;
	for(int i = 0;i <= 1;i++){
		for(int j = 0;j <= 1;j++){
			tmp.m[i][j] = 0;
		}
	}
	for(int i = 0;i <= 1;i++){
		for(int j = 0;j <= 1;j++){
			for(int k = 0;k <= 1;k++){
				tmp.m[i][j] = (tmp.m[i][j] + (a.m[i][k] * b.m[k][j] % mod)) % mod;// 矩阵乘法 
			}
		}
	}
	return tmp;
}

node qpow(node a,ll b){
	node r;//
	r.m[0][0] = r.m[1][1] = 1;
	r.m[0][1] = r.m[1][0] = 0;
	while(b){
		if(b & 1) r = mul(res,a);
		b >>= 1;
		a = mul(a,a);
	}
	return res;
}

int main(){
	cin>>a>>b>>n;
	if(n == 1){
		ll ans = (2*a) % mod;
		printf("%lld\n",ans);
	}
	else if(n == 2){
		ll ans = (2*a*a+2*b)%mod;
		printf("%lld\n",ans);
	}
	else{
		res.m[0][0] = (2*a % mod); res.m[0][1]=((b - a*a)%mod+mod) % mod;//递推式 
		res.m[1][0] = 1;     res.m[1][1] = 0;
		ans.m[0][0] = (2 * a * a + 2 * b) % mod;
		ans.m[1][0] = (2 * a) % mod;
		ans.m[0][1] = ans.m[1][1] = 0;
		res = qpow(res,n - 2);
		ans = mul(res,ans);
		printf("%lld\n",ans.m[0][0]);
	}
	return 0;
}

D. Divide and Merge

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define rg register
using namespace std;
typedef long long ll;
int sread()
{
	int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar(); }
	while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	return f*x; 
}
int n,jishu_,oushu_;
int a[100010];
int main()
{
	n=sread();
	for(rg int i=1;i<=n;++i)
	{
		a[i]=sread();
		if(a[i]%2&&a[i]!=1) jishu_++;
		else if(a[i]%2==0) oushu_++;
	}
//	cout<<jishu_<<"　"<<oushu_<<endl; 
	if(jishu_==0 && oushu_==0) //1111 先手失败 后手胜利 
		printf("Bob\n");
	else if(oushu_%2==0) //先手必胜 
		printf("Alice\n");
	else printf("Bob\n"); //若以上两种均不成立，则后手具有必胜策略 
	return 0;
}