結果
問題 | No.1655 123 Swaps |
ユーザー |
👑 |
提出日時 | 2021-08-21 02:25:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 10,833 bytes |
コンパイル時間 | 1,177 ms |
コンパイル使用メモリ | 109,696 KB |
実行使用メモリ | 13,516 KB |
最終ジャッジ日時 | 2024-10-14 11:03:01 |
合計ジャッジ時間 | 3,684 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <cassert>#include <cmath>#include <cstdint>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <functional>#include <iostream>#include <map>#include <numeric>#include <queue>#include <set>#include <sstream>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;using Int = long long;template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }////////////////////////////////////////////////////////////////////////////////template <unsigned M_> struct ModInt {static constexpr unsigned M = M_;unsigned x;constexpr ModInt() : x(0U) {}constexpr ModInt(unsigned x_) : x(x_ % M) {}constexpr ModInt(unsigned long long x_) : x(x_ % M) {}constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }ModInt pow(long long e) const {if (e < 0) return inv().pow(-e);ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;}ModInt inv() const {unsigned a = M, b = x; int y = 0, z = 1;for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }assert(a == 1U); return ModInt(y);}ModInt operator+() const { return *this; }ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }explicit operator bool() const { return x; }bool operator==(const ModInt &a) const { return (x == a.x); }bool operator!=(const ModInt &a) const { return (x != a.x); }friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }};////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// M: prime, G: primitive root, 2^K | M - 1template <unsigned M_, unsigned G_, int K_> struct Fft {static_assert(2U <= M_, "Fft: 2 <= M must hold.");static_assert(M_ < 1U << 30, "Fft: M < 2^30 must hold.");static_assert(1 <= K_, "Fft: 1 <= K must hold.");static_assert(K_ < 30, "Fft: K < 30 must hold.");static_assert(!((M_ - 1U) & ((1U << K_) - 1U)), "Fft: 2^K | M - 1 must hold.");static constexpr unsigned M = M_;static constexpr unsigned M2 = 2U * M_;static constexpr unsigned G = G_;static constexpr int K = K_;ModInt<M> FFT_ROOTS[K + 1], INV_FFT_ROOTS[K + 1];ModInt<M> FFT_RATIOS[K], INV_FFT_RATIOS[K];Fft() {const ModInt<M> g(G);for (int k = 0; k <= K; ++k) {FFT_ROOTS[k] = g.pow((M - 1U) >> k);INV_FFT_ROOTS[k] = FFT_ROOTS[k].inv();}for (int k = 0; k <= K - 2; ++k) {FFT_RATIOS[k] = -g.pow(3U * ((M - 1U) >> (k + 2)));INV_FFT_RATIOS[k] = FFT_RATIOS[k].inv();}assert(FFT_ROOTS[1] == M - 1U);}// as[rev(i)] <- \sum_j \zeta^(ij) as[j]void fft(ModInt<M> *as, int n) const {assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << K);int m = n;if (m >>= 1) {for (int i = 0; i < m; ++i) {const unsigned x = as[i + m].x; // < Mas[i + m].x = as[i].x + M - x; // < 2 Mas[i].x += x; // < 2 M}}if (m >>= 1) {ModInt<M> prod = 1U;for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {for (int i = i0; i < i0 + m; ++i) {const unsigned x = (prod * as[i + m]).x; // < Mas[i + m].x = as[i].x + M - x; // < 3 Mas[i].x += x; // < 3 M}prod *= FFT_RATIOS[__builtin_ctz(++h)];}}for (; m; ) {if (m >>= 1) {ModInt<M> prod = 1U;for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {for (int i = i0; i < i0 + m; ++i) {const unsigned x = (prod * as[i + m]).x; // < Mas[i + m].x = as[i].x + M - x; // < 4 Mas[i].x += x; // < 4 M}prod *= FFT_RATIOS[__builtin_ctz(++h)];}}if (m >>= 1) {ModInt<M> prod = 1U;for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {for (int i = i0; i < i0 + m; ++i) {const unsigned x = (prod * as[i + m]).x; // < Mas[i].x = (as[i].x >= M2) ? (as[i].x - M2) : as[i].x; // < 2 Mas[i + m].x = as[i].x + M - x; // < 3 Mas[i].x += x; // < 3 M}prod *= FFT_RATIOS[__builtin_ctz(++h)];}}}for (int i = 0; i < n; ++i) {as[i].x = (as[i].x >= M2) ? (as[i].x - M2) : as[i].x; // < 2 Mas[i].x = (as[i].x >= M) ? (as[i].x - M) : as[i].x; // < M}}// as[i] <- (1/n) \sum_j \zeta^(-ij) as[rev(j)]void invFft(ModInt<M> *as, int n) const {assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << K);int m = 1;if (m < n >> 1) {ModInt<M> prod = 1U;for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {for (int i = i0; i < i0 + m; ++i) {const unsigned long long y = as[i].x + M - as[i + m].x; // < 2 Mas[i].x += as[i + m].x; // < 2 Mas[i + m].x = (prod.x * y) % M; // < M}prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];}m <<= 1;}for (; m < n >> 1; m <<= 1) {ModInt<M> prod = 1U;for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {for (int i = i0; i < i0 + (m >> 1); ++i) {const unsigned long long y = as[i].x + M2 - as[i + m].x; // < 4 Mas[i].x += as[i + m].x; // < 4 Mas[i].x = (as[i].x >= M2) ? (as[i].x - M2) : as[i].x; // < 2 Mas[i + m].x = (prod.x * y) % M; // < M}for (int i = i0 + (m >> 1); i < i0 + m; ++i) {const unsigned long long y = as[i].x + M - as[i + m].x; // < 2 Mas[i].x += as[i + m].x; // < 2 Mas[i + m].x = (prod.x * y) % M; // < M}prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];}}if (m < n) {for (int i = 0; i < m; ++i) {const unsigned y = as[i].x + M2 - as[i + m].x; // < 4 Mas[i].x += as[i + m].x; // < 4 Mas[i + m].x = y; // < 4 M}}const ModInt<M> invN = ModInt<M>(n).inv();for (int i = 0; i < n; ++i) {as[i] *= invN;}}void fft(vector<ModInt<M>> &as) const {fft(as.data(), as.size());}void invFft(vector<ModInt<M>> &as) const {invFft(as.data(), as.size());}vector<ModInt<M>> convolve(vector<ModInt<M>> as, vector<ModInt<M>> bs) const {if (as.empty() || bs.empty()) return {};const int len = as.size() + bs.size() - 1;int n = 1;for (; n < len; n <<= 1) {}as.resize(n); fft(as);bs.resize(n); fft(bs);for (int i = 0; i < n; ++i) as[i] *= bs[i];invFft(as);as.resize(len);return as;}vector<ModInt<M>> square(vector<ModInt<M>> as) const {if (as.empty()) return {};const int len = as.size() + as.size() - 1;int n = 1;for (; n < len; n <<= 1) {}as.resize(n); fft(as);for (int i = 0; i < n; ++i) as[i] *= as[i];invFft(as);as.resize(len);return as;}};const Fft<924844033U, 5U, 21> FFT;constexpr unsigned MO = FFT.M;using Mint = ModInt<MO>;constexpr int LIM = 600'010;Mint inv[LIM], fac[LIM], invFac[LIM];void prepare() {inv[1] = 1;for (int i = 2; i < LIM; ++i) {inv[i] = -((Mint::M / i) * inv[Mint::M % i]);}fac[0] = invFac[0] = 1;for (int i = 1; i < LIM; ++i) {fac[i] = fac[i - 1] * i;invFac[i] = invFac[i - 1] * inv[i];}}Mint binom(Int n, Int k) {if (n < 0) {if (k >= 0) {return ((k & 1) ? -1 : +1) * binom(-n + k - 1, k);} else if (n - k >= 0) {return (((n - k) & 1) ? -1 : +1) * binom(-k - 1, n - k);} else {return 0;}} else {if (0 <= k && k <= n) {assert(n < LIM);return fac[n] * invFac[k] * invFac[n - k];} else {return 0;}}}int A, B, C;int main() {prepare();for (; ~scanf("%d%d%d", &A, &B, &C); ) {Mint ans = 0;if ((A + B + C) % 2 == 0) {const int N = (A + B + C) / 2;for (int rb = 0; rb < 3; ++rb) {const int rc = (B + rb - C % 3 + 3) % 3;vector<Mint> fs(B / 3 + 1, 0);vector<Mint> gs(C / 3 + 1, 0);for (int i = 0, b; (b = 3 * i + rb) <= B; ++i) fs[i] = invFac[b] * invFac[B - b];for (int i = 0, c; (c = 3 * i + rc) <= C; ++i) gs[i] = invFac[c] * invFac[C - c];const auto prod = FFT.convolve(fs, gs);for (int i = 0; i < (int)prod.size(); ++i) {const int a = N - (3 * i + rb + rc);if (0 <= a && a <= A) {ans += invFac[a] * invFac[A - a] * prod[i];}}}ans *= fac[N];ans *= fac[N];/*Mint brt = 0;for (int a = 0; a <= A; ++a) for (int b = 0; b <= B; ++b) for (int c = 0; c <= C; ++c) {if (a + b + c == N && (B + b - C - c) % 3 == 0) {Mint tmp = 1;tmp *= fac[N] * invFac[a] * invFac[b] * invFac[c];tmp *= fac[N] * invFac[A - a] * invFac[B - b] * invFac[C - c];brt += tmp;}}cerr<<"brt = "<<brt<<endl;//*/}printf("%u\n", ans.x);}return 0;}