Submission #67787261

---

Source Code Expand

// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <array>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define tisic 47
#define soclose 1e-8
#define patkan 9
#define ff first
#define ss second
using uint = unsigned int;
using cat = long long;
using dbl = long double;
constexpr dbl pi = 3.14159265358979323846;
using namespace std;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

template <typename T>
T abs(T x) { return (x < 0) ? (-x) : x; }

cat gcd(cat a, cat b) {
	if(a > b) swap(a, b);
	while(a) {
		cat c = b%a;
		b = a;
		a = c;
	}
	return b;
}

cat pw(cat a, cat e, cat mod) {
	if(e <= 0) return 1;
	cat x = pw(a, e/2, mod);
	x = x * x % mod;
	return (e&1) ? x * a % mod : x;
}

template <typename T>
class fin {
	vector<T> node_val;

	int lastone(int x) { return x & (x ^ (x-1)); }

public:
	fin(int N, T init_val) {
		node_val.resize(N+10, init_val);
	}

	void put(int pos, T val) {
		for(int i = pos+1; i < (int)node_val.size(); i += lastone(i))
			node_val[i] += val;
	}

	T get(int pos) {
		T ret = 0;
		for(int i = pos+1; i > 0; i -= lastone(i))
			ret += node_val[i];
		return ret;
	}
};

constexpr cat MOD = 998244353;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed << setprecision(12);
	int H, W;
	cin >> H >> W;
	if(H%2 == 0) {
		cout << "0\n";
		return 0;
	}
	vector<cat> fac(2*H+1, 1);
	for(int i = 1; i <= 2*H; i++) fac[i] = fac[i-1] * i % MOD;
	vector<cat> fac_inv(2*H+1);
	fac_inv[2*H] = pw(fac[2*H], MOD-2, MOD);
	for(int i = 2*H; i > 0; i--) fac_inv[i-1] = fac_inv[i] * i % MOD;
	if(W%2 != 0) {
		cat ans = 0;
		for(int np = 0; np <= H; np++) {
			int d = (np - (H-np)) % W;
			if(d < 0) d += W;
			if(d == 0 || gcd(d, W) != 1) continue;
			ans = (ans + fac[H] * fac_inv[np] % MOD * fac_inv[H-np]) % MOD;
		}
		cout << ans << "\n";
	}
	else {
		cat ans = 0;
		for(int d0 = 1; d0 <= H; d0++) { // np - nm
			int d = d0 % (W/2);
			if(d < 0) d += (W/2);
			if(d == 0 || gcd(d, W/2) != 1) continue;
			ans = (ans + 2 * fac[2*H] * fac_inv[H+d0] % MOD * fac_inv[H-d0]) % MOD;
		}
		cout << ans << "\n";
	}
}

// look at my code
// my code is amazing

Submission Info

Judge Result