2023牛客多校第一场

Qiansui / 2023-07-19 / 原文

牛客多校第一场
D 题
H 题
J 题

牛客多校第一场

比赛地址：传送门

D 题

题意：
有一个 \(n \times m\) 的网格，每格放了块巧克力。Walk Alone（懵哥）和 Kelin 轮流吃巧克力，Kelin 先吃。每轮一个人能选择一个左下角为(1,1)的子矩形，把里面的巧克力吃光，且至少要吃一个，吃到最后一个巧克力的人输。问懵哥和 Kelin 谁赢。

思路：
1x1后手赢，其他情况先手赢。怎么理解？依旧是必胜态与必败态的转移。
如果说当前 n=1 且 m=1，那么先手必先取而输；剩下的情况，如果说先手先取(1,1)，那么后手再取一手时如果说后手进入必胜态，那么其实在之前先手选择的时候就可以选择这一手并让后手进入必败态，所以说别的情况下先手必胜。

//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
//#define int long long

using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ull,ull> pull;
typedef pair<double,double> pdd;
/*
1x1后手赢，其他情况先手赢
*/
const int maxm=2e5+5,inf=0x3f3f3f3f,mod=998244353;

void solve(){
	int n,m;
	cin>>n>>m;
	if(n==1 && m==1) cout<<"Walk Alone\n";
	else cout<<"Kelin\n";
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
	// cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

H 题

题解(来自changge)
还有个22级的离谱思路，双重循环+限制循环次数即得解

J 题

题意：

思路：
~~再理解理解~~
概率递推式
打时具体的过程都想清楚了，但是欠点实现的思路qwq
下为代码（来自队友）

//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
//#define int long long

using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ull,ull> pull;
typedef pair<double,double> pdd;
/*

*/
const int maxm = 2e5+5, inf = 0x3f3f3f3f, mod = 998244353;

ll qpow(ll a,ll x){
	ll res = 1;
	while(x){
		if(x & 1) res = res * a % mod;
		a = a * a % mod;
		x >>= 1;
	}
	return res;
}

void solve(){
	ll n, m;
	cin >> n >> m;
	ll t = n, ans = 1;
	while(t < n + m){
		ll lg = log2(t + 1), r = min(m + n, (1ll << (lg + 1)) - 1);
		ans *= qpow(mod + 1 - qpow(2, mod - 1 - lg), r - t);
		ans %= mod;
		t = r;
	}
	cout << ans <<'\n';
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _ = 1;
	// cin >> _;
	while(_--){
		solve();
	}
	return 0;
}