こういう数え上げ、大好きすぎる!!!
問題概要
長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。
- となる を選んで
- += 2 とする
- += 1 とする
制約
考えたこと
こういうのは「まず判定問題を解く」のが良いと相場は決まっている!!!つまり操作によって数列 を作れるかどうかを判定するのだ。
まず自明な必要条件として
がある。しかしこれだけではダメなケースもある。たとえば 、 のとき
は作れない。なぜなら を合計 箇所で足さないとダメだけど、 箇所も足せないのだ。よって次の条件も追加!!
- のうち奇数が 個以下
これを満たさないと を 箇所以上で行うことができない。逆にこれまでの条件をすべて満たしていれば、「+2」を 箇所定めることができて、残りは「+1」をよしなに埋めれば OK。
以上から、必要十分条件がわかりやすく特徴づけられた!これを満たす数列 の個数を求めればよい。
- は非負整数
- のうち奇数が 個以下
数列の個数
安直には
- dp[ i ][ j ][ k ] := 数列の最初の i 個について、奇数が j 個で、総和が k となる場合の数
という DP で で解ける。でもこの方向性では到底高速化できなさそう。ちょっと作戦を変更して、重複組合せを活用する方向性で考えてみる。
奇数が 個のとき、 個のうちどれが奇数かを決め打ちする方法が 通りになる。それらの奇数については 1 を引けば「すべて偶数」という条件に書き変わるので 2 で割ってしまう。そうすると次の数え上げ問題に帰着される。
- は非負整数
- ( とする)
- ( 箇所分)
- ( 箇所分)
といった条件は扱いづらいので包除原理することを考える。 であれば、2 箇所以上で条件を破ることはないので、次のようにすぐ求められる。
- 全体: 通り
- 制約破り: + 通り
の場合は別途求めることにした。計算量は 。
コード
#include <bits/stdc++.h> using namespace std; // modint template<int MOD> struct Fp { long long val; constexpr Fp(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; } constexpr int getmod() const { return MOD; } 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 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 { if (n == 0) return 1; if (n < 0) return modpow(modinv(r), -n); auto t = modpow(r, n / 2); t = t * t; if (n & 1) t = t * r; return t; } friend constexpr Fp<MOD> modinv(const Fp<MOD>& 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); } return Fp<MOD>(u); } }; const int MOD = 998244353; using mint = Fp<MOD>; // 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].getmod(); 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]; } }; BiCoef<mint> bc; mint solve(int N, int M) { if (M == 1) return mint(N) * (N-1); mint res = 0; for (int k = 0; k <= min(M, N); ++k) { if ((M*3-k) % 2 == 1) continue; int A = (M*3-k) / 2; mint all = bc.com(A+N-1, N-1); mint sum1 = bc.com(A-M+N-1, N-1) * k; mint sum2 = bc.com(A-M+N-2, N-1) * (N-k); mint tmp = all - sum1 - sum2; res += tmp * bc.com(N, k); } return res; } int main() { int N, M; cin >> N >> M; bc.init(N + M*3 + 1); cout << solve(N, M) << endl; }