C. Darkness I

首先根据短边放一条对角线，然后往后每隔一列只放一个即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    cout << (n + m + 1) / 2;
    return 0;
}

H. Binary Craziness

因为是树的关系，度数的种类并不会太多，直接枚举度数就好了。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod = 998244353;

int32_t main(){
	ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
	int n , m ;
	cin >> n >> m;
	vector<int> deg( n + 1 );
	for( int x , y ; m ; m -- ){
		cin >> x >> y;
		deg[x] ++ , deg[y] ++;
	}
	unordered_map<int,int> cnt;
	for( int i = 1 ; i <= n ; i ++ )
		cnt[ deg[i] ] ++;
	int res = 0;
	vector<int> a , b;
	for( const auto &[ x , y ] : cnt ) a.push_back(x) , b.push_back(y);
	
	for( int i = 0 ; i < a.size() ; i ++ )
		for( int j = i+1 ; j < a.size() ; j ++ ){
			(res += (a[i] ^ a[j])*(a[i] | a[j])%mod*(a[i] & a[j])%mod*b[i]%mod*b[j]%mod)%=mod;
		}
	cout << res <<"\n";
	return 0;
}

I. Step

首先\(lcm(p_1,\cdots,p_n)\)的倍数天一定可以回到\(1\)。前\(i\)天累计移动\(\frac{i(i+1)}{2}\)步，所以要寻找最小的\(i\)满足\(\frac{i(i+1)}{2} = k\times lcm\)

可以变形为\(i(i+1)=k(2lcm)\)，把\(2lcm\)进行质因数分解，可以估算出质因子的数目不超过20 个，因为相邻数互质，每一个数只能属于\(i\)或\(i+1\)中的一个。所以可以通过二进制枚举的形式，设属于\(i\)的质因子乘积为\(y\)，属于\(i+1\)的质因子乘积为\(x\)。同理也可以吧\(k\)质因数分解，然后分给\(i+1\)乘积为\(a\)，分给\(i\)的乘积是\(b\)。所以可以得到\(ax-by=1\)，用扩展欧几里得借一下方程就好了。

#include <bits/stdc++.h>
using namespace std;

#define int long long


int power( int x , int y ){
    int ans = 1;
    while( y ){
        if( y & 1 ) ans = ans * x;
        y >>= 1 , x = x * x;
    }
    return ans;
}


int exgcd( int a , int b , int & x , int & y ){
    if( b == 0 ) { x = 1 , y = 0 ; return a;}
    int d = exgcd( b , a%b , x , y );
    int z = x ; x = y ; y = z - y * (a / b);
    return d;
}


int32_t main(){
    ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
    int n;
    cin >> n;

    unordered_map<int,int> prime;

    for( int i = 1 , x ; i <= n ; i ++ ){
        cin >> x;
        for( int j = 2 , cnt ; j*j <= x; j ++ ){
            if( x % j == 0 ){
                cnt = 0;
                while( x % j == 0 ) x /= j , cnt ++;
                prime[j] = max( prime[j] , cnt );
            }
        }
        if( x > 1 ) prime[x] = max( prime[x] , 1ll );
    }

    vector<int> a;
    prime[2] ++;
    for( const auto & [ x , y ] : prime )
        a.push_back( power( x , y ) );

    int res = LLONG_MAX;

    for( int i = 0 , m = (1ll<<a.size())-1 , x , y , t ; i <= m ; i ++ ){
        x = y = 1 , t = i;
        for( int j = 0 ; j < a.size() ; j ++ , t >>= 1){
            if( t & 1 ) x *= a[j];
            else y *= a[j];
        }
        int kx , ky , d ;

        d = exgcd( x , -y , kx , ky );
        if( kx && ky && d ) res = min( res , ky * y) ;
    }
    cout << res;

    return 0;
}

F. Inverse Manacher

找到枚举|的位置，如果f[i]=1所有左右两侧的字母不同。固定第一个字母，然后根据这个规律构造即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n, m = n * 2 + 2;
    vector<int> a(m+1);
    for( int i = 1 ; i <= m ; i ++ ) cin >> a[i];
    cout << "a";
    for( int i = 4 , t = 0 ; i < m ; i += 2 ){
        if( a[i] == 1 ) t ^= 1;
        cout << "ab"[t];
    }
    return 0;
}

J. Expansion

贪心吧。维护一下前缀和中的最大值，如果过不去了就在最大值处多停留几次。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, res = 0;
    cin >> n;
    for (int i = 1, x, sum = 0, large = 0, cnt = 0, p; i <= n; i++) {
        cin >> x;

        sum += x;
        if (sum < 0 && (i == n || i == 1)) {
            cout << "-1\n";
            return 0;
        }
        large = max(large, sum);
        if (cnt + sum >= 0) {
            res++;
            cnt += sum;
        } else {
            p = -cnt - sum;
            if (large == 0) {
                cout << "-1\n";
                return 0;
            }
            p = (p + large - 1) / large;
            cnt += large * p + sum;
            res += p + 1;
        }
    }
    cout << res;
    return 0;
}

K. Dice Game

对于\([2,n+1]\)号人对游戏的贡献是相同的，所以单独考虑即可。如果1号要输，则必须输给所有的人。

对于1号，当他固定投出\(i\)的时候，2 号和他平局的概率是\(\frac{1}{m}\)，2 号获胜的概率是\(\frac{m-i}{m}\)，所以2号在第\(x\)局获胜的概率是\(\frac{m-i}{m^x}\)，所以2 号获胜的概率是\(\sum_{x=1}^{+\infty}\frac{m-i}{m^x}=\frac{m-x}{m-1}\)。所以\(n\)个人获胜的概率是\((\frac{m-i}{m-1})^n\)。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod = 998244353;

int power( int x , int y ){
	int ans = 1;
	while( y ){
		if( y & 1 ) ans = ans * x % mod;
		y >>= 1 , x = x * x % mod;
	}
	return ans;
}

int inv( int x ){
	return power( x , mod - 2 );
}

int32_t main(){
	ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
	int n , m ;
	cin >> n >> m;
	
	int invs = inv( m-1 );
	for( int i = 1 ; i <= m ; i ++ ){
		cout << power((m-i) * invs%mod , n ) << " ";
	}
	return 0;
}

M. Different Billing

鸡兔同笼？枚举一下就好了。

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int x , y;
    cin >> x >> y;
    for( int a , b = 0 , c ; b <= x ; b ++ ){
        c = y - b * 1000;
        if( c % 2500 ) continue;
        c /= 2500 , a = x - b - c;
        if( a < 0 || c < 0 ) continue;
        cout << a << " " << b << " " << c;
        return 0;
    }
    cout << "-1\n";
    return 0;
}