FPS + 負の二項係数
問題概要
長さが で総和が であるような、正の整数のみからなる数列 すべてについての
の総和を 998244353 で割ったあまりを求めよ ( ケース)。
制約
解法 (1):FPS
求めたいものは
である。これはちゃんと計算すると、
を求めればよいことになる。これは負の二項係数だ。形式的に書くと、負の二項係数 を用いて、
を求めたい。一般に
となる。よって、我々が求めたいものは
となる。
解法 (2):積の和
この問題を単純化した問題
同じ数列群に対する
の総和を求めよ
という問題は、最も典型的な「積の和」の問題例としてよく知られている。
これと同じように解ける。まず、次のように式変形する。
こうすると、次の問題と一緒になる。
マス数 のテープを 個に分割し、各テープごとに 2 マス選んで色付けしていく方法は何通りか?
それに をかけた値を答えよ。
これは、分割のための 個の仕切りを追加してあげると、次の問題と一緒になる。
個のボールがある。これらのボールのうち、 個は赤色であり、残りの 個は白色である。
これらのボールを並び替える方法は何通りあるか?
それに をかけた値を答えよ。
この答えは、 となる。解法 (1) と同じ結論が得られた。
コード
#include <bits/stdc++.h> using namespace std; // modint template<int MOD> struct Fp { // inner value long long val; // constructor constexpr Fp() noexcept : val(0) { } constexpr Fp(long long v) noexcept : val(v % MOD) { if (val < 0) val += MOD; } constexpr long long get() const noexcept { return val; } constexpr int get_mod() const noexcept { return MOD; } // arithmetic operators constexpr Fp operator - () const noexcept { return val ? MOD - val : 0; } constexpr Fp operator + (const Fp &r) const noexcept { return Fp(*this) += r; } constexpr Fp operator - (const Fp &r) const noexcept { return Fp(*this) -= r; } constexpr Fp operator * (const Fp &r) const noexcept { return Fp(*this) *= r; } constexpr Fp operator / (const Fp &r) const noexcept { return Fp(*this) /= r; } constexpr Fp& operator += (const Fp &r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr Fp& operator -= (const Fp &r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr Fp& operator *= (const Fp &r) noexcept { val = val * r.val % MOD; return *this; } constexpr Fp& operator /= (const Fp &r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr Fp pow(long long n) const noexcept { Fp res(1), mul(*this); while (n > 0) { if (n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } constexpr Fp inv() const noexcept { Fp res(1), div(*this); return res / div; } // other operators constexpr bool operator == (const Fp &r) const noexcept { return this->val == r.val; } constexpr bool operator != (const Fp &r) const noexcept { return this->val != r.val; } friend constexpr istream& operator >> (istream &is, Fp<MOD> &x) noexcept { is >> x.val; x.val %= MOD; if (x.val < 0) x.val += MOD; return is; } friend constexpr ostream& operator << (ostream &os, const Fp<MOD> &x) noexcept { return os << x.val; } friend constexpr Fp<MOD> modpow(const Fp<MOD> &r, long long n) noexcept { return r.pow(n); } friend constexpr Fp<MOD> modinv(const Fp<MOD> &r) noexcept { return r.inv(); } }; // Binomial coefficient template<class T> struct BiCoef { vector<T> fact_, inv_, finv_; constexpr BiCoef() {} constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) { init(n); } constexpr void init(int n) noexcept { fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1); int MOD = fact_[0].get_mod(); for(int i = 2; i < n; i++){ fact_[i] = fact_[i-1] * i; inv_[i] = -inv_[MOD%i] * (MOD/i); finv_[i] = finv_[i-1] * inv_[i]; } } constexpr T com(int n, int k) const noexcept { if (n < k || n < 0 || k < 0) return 0; return fact_[n] * finv_[k] * finv_[n-k]; } constexpr T fact(int n) const noexcept { if (n < 0) return 0; return fact_[n]; } constexpr T inv(int n) const noexcept { if (n < 0) return 0; return inv_[n]; } constexpr T finv(int n) const noexcept { if (n < 0) return 0; return finv_[n]; } }; int main() { const int MOD = 998244353, MAX = 610000; using mint = Fp<MOD>; BiCoef<mint> bc(MAX); int T; cin >> T; while (T--) { int M, N; cin >> N >> M; cout << modpow(mint(2), N) * bc.com(M + N*2 - 1, M - N) << endl; } }