Submission #36275343

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

namespace acah
{
	constexpr int maxn = 1e7 + 7;
	constexpr int p = 998244353;
	
	int N, M, ans, fac[maxn << 1], inv[maxn << 1], pf[maxn / 3];
	
	inline int C(int n, int m) {return 1ll * fac[n] * inv[m] % p * inv[n - m] % p;}
	
	int work()
	{
		ios::sync_with_stdio(false), cin.tie(nullptr);
		
		cin >> N >> M;
		
		*fac = 1;
		for(int i = 1; i <= N + M; i++) fac[i] = 1ll * fac[i - 1] * i % p;
		for(int t = inv[N + M] = fac[N + M], x = p - 3; x; t = 1ll * t * t % p, x >>= 1)
			if(x & 1) inv[N + M] = 1ll * inv[N + M] * t % p;
		for(int i = N + M - 1; ~i; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % p;
		*pf = 1;
		for(int i = 1; i <= M / 3; i++)
			pf[i] = pf[i - 1] + C(N + i - 1, N - 1), pf[i] -= (pf[i] >= p ? p : 0);
		
		for(int fs = 0, t; fs < 3; fs++) for(int cnt = N - 1; ~cnt; cnt--) {
			if((t = fs + (N - 1) * 2 - cnt) > M) break;
			ans += 1ll * pf[(M - t) / 3] * C(N - 1, cnt) % p, ans -= (ans >= p ? p : 0);
		}
		
		cout << ans;
		
		return 0;
	}
}

int main() {return acah::work();}

Submission Info

Judge Result