Submission #2277566


Source Code Expand

#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

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

cat mod = 998244353;

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

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N, M;
	cin >> N >> M;
	int sz = max(N, M);
	vector<cat> fac(N+M+1, 1), inv(N+M+1, 1), invn(N+M+1, 1);
	cat inv2 = pw(2, mod-2);
	for(int i = 1; i <= N+M; i++) {
		fac[i] = (i * fac[i-1]) % mod;
		if(i%2 == 0) invn[i] = inv2 * invn[i/2] % mod;
		else invn[i] = pw(i, mod-2);
		inv[i] = (invn[i] * inv[i-1]) % mod;
	}
	vector<cat> H(sz+1, 0), P(sz+1, 0);
	for(int i = 0; i <= N; i++) H[i] = inv[N-i] * inv[i] % mod;
	for(int i = 1; i <= M; i++) P[i] = inv[M-i] * inv[i-1] % mod;
	cat ans = 0, cnt = 0;
	for(int k = 0; k < 2; k++) {
		cnt = 0;
		M--;
		for(int i = 0; i <= N+M; i++) {
			if(i%2 != 0) {
				if((i-1)/2 <= M && (i+1)/2 <= N)
					cnt = (cnt - fac[N+M-i] % mod * inv[M-(i-1)/2] % mod * inv[N-(i+1)/2] % mod * fac[i-1] % mod * inv[i/2] % mod * inv[i/2]) % mod;
			}
			else {
				if(i/2 <= M && i/2 <= N)
					cnt = (cnt + fac[N+M-i] % mod * inv[M-i/2] % mod * inv[N-i/2] % mod * ((i == 0) ? 1 : (fac[i-1] * inv[i/2-1] % mod * inv[i/2] % mod))) % mod;
			}
			ans += cnt;
		}
		M++;
		swap(M, N);
	}
	for(int s = 2; s <= min(N, M) * 2; s += 2)
		ans += inv[N-s/2] * inv[s/2] % mod * inv[s/2-1] % mod * inv[M-s/2] % mod * fac[s-1] % mod * fac[N+M-s] % mod;
	ans %= mod;
	ans = (ans * inv[N+M] % mod * fac[N] % mod * fac[M]) % mod;
	if(ans < 0) ans += mod;
	cout << ans << "\n";
	return 0;}

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

Submission Info

Submission Time
Task F - Yes or No
User xellos
Language C++14 (GCC 5.4.1)
Score 2000
Code Size 2532 Byte
Status AC
Exec Time 701 ms
Memory 31488 KB

Judge Result

Set Name Sample Partial All
Score / Max Score 0 / 0 1500 / 1500 500 / 500
Status
AC × 5
AC × 28
AC × 75
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt
Partial sample_01.txt, sample_02.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_2_01.txt, subtask_2_02.txt, subtask_2_03.txt, subtask_2_04.txt, subtask_2_05.txt, subtask_2_06.txt, subtask_2_07.txt, subtask_2_08.txt, subtask_2_09.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_28.txt, subtask_2_29.txt, subtask_2_30.txt, subtask_2_31.txt, subtask_2_32.txt, subtask_2_33.txt, subtask_2_34.txt, subtask_2_35.txt, subtask_2_36.txt, subtask_2_37.txt, subtask_2_38.txt, subtask_2_39.txt, subtask_2_40.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 1 ms 256 KB
sample_05.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 256 KB
subtask_1_03.txt AC 1 ms 256 KB
subtask_1_04.txt AC 1 ms 256 KB
subtask_1_05.txt AC 1 ms 256 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 1 ms 256 KB
subtask_1_08.txt AC 1 ms 256 KB
subtask_1_09.txt AC 1 ms 256 KB
subtask_1_10.txt AC 2 ms 256 KB
subtask_1_11.txt AC 3 ms 384 KB
subtask_1_12.txt AC 5 ms 384 KB
subtask_1_13.txt AC 15 ms 896 KB
subtask_1_14.txt AC 43 ms 2176 KB
subtask_1_15.txt AC 141 ms 6528 KB
subtask_1_16.txt AC 141 ms 6528 KB
subtask_1_17.txt AC 141 ms 6528 KB
subtask_1_18.txt AC 144 ms 6528 KB
subtask_1_19.txt AC 141 ms 6528 KB
subtask_1_20.txt AC 141 ms 6528 KB
subtask_1_21.txt AC 141 ms 6528 KB
subtask_1_22.txt AC 142 ms 6528 KB
subtask_1_23.txt AC 140 ms 6400 KB
subtask_1_24.txt AC 129 ms 6016 KB
subtask_1_25.txt AC 125 ms 5760 KB
subtask_2_01.txt AC 1 ms 256 KB
subtask_2_02.txt AC 1 ms 256 KB
subtask_2_03.txt AC 1 ms 256 KB
subtask_2_04.txt AC 700 ms 31488 KB
subtask_2_05.txt AC 699 ms 31488 KB
subtask_2_06.txt AC 699 ms 31488 KB
subtask_2_07.txt AC 700 ms 31488 KB
subtask_2_08.txt AC 700 ms 31488 KB
subtask_2_09.txt AC 699 ms 31488 KB
subtask_2_10.txt AC 700 ms 31488 KB
subtask_2_11.txt AC 699 ms 31488 KB
subtask_2_12.txt AC 700 ms 31488 KB
subtask_2_13.txt AC 701 ms 31488 KB
subtask_2_14.txt AC 699 ms 31488 KB
subtask_2_15.txt AC 699 ms 31488 KB
subtask_2_16.txt AC 700 ms 31488 KB
subtask_2_17.txt AC 690 ms 31104 KB
subtask_2_18.txt AC 640 ms 29056 KB
subtask_2_19.txt AC 546 ms 24704 KB
subtask_2_20.txt AC 258 ms 19840 KB
subtask_2_21.txt AC 258 ms 19840 KB
subtask_2_22.txt AC 259 ms 19840 KB
subtask_2_23.txt AC 259 ms 19840 KB
subtask_2_24.txt AC 259 ms 19840 KB
subtask_2_25.txt AC 259 ms 19840 KB
subtask_2_26.txt AC 259 ms 19840 KB
subtask_2_27.txt AC 261 ms 19840 KB
subtask_2_28.txt AC 267 ms 20096 KB
subtask_2_29.txt AC 276 ms 20224 KB
subtask_2_30.txt AC 347 ms 22144 KB
subtask_2_31.txt AC 434 ms 24448 KB
subtask_2_32.txt AC 700 ms 31488 KB
subtask_2_33.txt AC 700 ms 31488 KB
subtask_2_34.txt AC 699 ms 31488 KB
subtask_2_35.txt AC 692 ms 31232 KB
subtask_2_36.txt AC 688 ms 31232 KB
subtask_2_37.txt AC 331 ms 16256 KB
subtask_2_38.txt AC 231 ms 15232 KB
subtask_2_39.txt AC 665 ms 30592 KB
subtask_2_40.txt AC 337 ms 21888 KB