Submission #19015882


Source Code Expand

Copy
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


struct ModInt(int M_) {
  import std.conv : to;
  alias M = M_;
  int x;
  this(ModInt a) { x = a.x; }
  this(long a) { x = cast(int)(a % M); if (x < 0) x += M; }
  ref ModInt opAssign(long a) { return (this = ModInt(a)); }
  ref ModInt opOpAssign(string op)(ModInt a) {
    static if (op == "+") { x += a.x; if (x >= M) x -= M; }
    else static if (op == "-") { x -= a.x; if (x < 0) x += M; }
    else static if (op == "*") { x = cast(int)((cast(long)(x) * a.x) % M); }
    else static if (op == "/") { this *= a.inv(); }
    else static assert(false);
    return this;
  }
  ref ModInt opOpAssign(string op)(long a) {
    static if (op == "^^") {
      if (a < 0) return (this = inv()^^(-a));
      ModInt t2 = this, te = ModInt(1);
      for (long e = a; e > 0; e >>= 1) {
        if (e & 1) te *= t2;
        t2 *= t2;
      }
      x = cast(int)(te.x);
      return this;
    } else return mixin("this " ~ op ~ "= ModInt(a)");
  }
  ModInt inv() const {
    int a = x, b = M, y = 1, z = 0, t;
    for (; ; ) {
      t = a / b; a -= t * b;
      if (a == 0) {
        assert(b == 1 || b == -1);
        return ModInt(b * z);
      }
      y -= t * z;
      t = b / a; b -= t * a;
      if (b == 0) {
        assert(a == 1 || a == -1);
        return ModInt(a * y);
      }
      z -= t * y;
    }
  }
  ModInt opUnary(string op: "-")() const { return ModInt(-x); }
  ModInt opBinary(string op, T)(T a) const {
    return mixin("ModInt(this) " ~ op ~ "= a");
  }
  ModInt opBinaryRight(string op)(long a) const {
    return mixin("ModInt(a) " ~ op ~ "= this");
  }
  bool opCast(T: bool)() const { return (x != 0); }
  string toString() const { return x.to!string; }
}

enum MO = 998244353;
alias Mint = ModInt!MO;


enum LIM = 2 * 10^^6 + 10;
Mint[] inv, fac, invFac;
void prepare() {
  inv = new Mint[LIM];
  fac = new Mint[LIM];
  invFac = new Mint[LIM];
  inv[1] = 1;
  foreach (i; 2 .. LIM) {
    inv[i] = -(Mint.M / i) * inv[cast(size_t)(Mint.M % i)];
  }
  fac[0] = invFac[0] = 1;
  foreach (i; 1 .. LIM) {
    fac[i] = fac[i - 1] * i;
    invFac[i] = invFac[i - 1] * inv[i];
  }
}
Mint binom(long n, long k) {

  //!!!
  if (n == -1 && k == -1) {
    return Mint(1);
  }

  if (0 <= k && k <= n) {
    assert(n < LIM);
    return fac[cast(size_t)(n)] * invFac[cast(size_t)(k)] * invFac[cast(size_t)(n - k)];
  } else {
    return Mint(0);
  }
}


// M: prime, G: primitive root
class Fft(int M_, int G, int K) {
  import std.algorithm : reverse;
  import std.traits : isIntegral;
  alias M = M_;
  // 1, 1/4, 1/8, 3/8, 1/16, 5/16, 3/16, 7/16, ...
  int[] gs;
  this() {
    static assert(2 <= K && K <= 30, "Fft: 2 <= K <= 30 must hold");
    static assert(!((M - 1) & ((1 << K) - 1)), "Fft: 2^K | M - 1 must hold");
    gs = new int[1 << (K - 1)];
    gs[0] = 1;
    long g2 = G, gg = 1;
    for (int e = (M - 1) >> K; e; e >>= 1) {
      if (e & 1) gg = (gg * g2) % M;
      g2 = (g2 * g2) % M;
    }
    gs[1 << (K - 2)] = cast(int)(gg);
    for (int l = 1 << (K - 2); l >= 2; l >>= 1) {
      gs[l >> 1] = cast(int)((cast(long)(gs[l]) * gs[l]) % M);
    }
    assert((cast(long)(gs[1]) * gs[1]) % M == M - 1,
           "Fft: g^(2^(K-1)) == -1 (mod M) must hold");
    for (int l = 2; l <= 1 << (K - 2); l <<= 1) {
      foreach (i; 1 .. l) {
        gs[l + i] = cast(int)((cast(long)(gs[l]) * gs[i]) % M);
      }
    }
  }
  void fft(int[] xs) const {
    const n = cast(int)(xs.length);
    assert(!(n & (n - 1)), "Fft.fft: |xs| must be a power of two");
    assert(n <= 1 << K, "Fft.fft: |xs| <= 2^K must hold");
    for (int l = n; l >>= 1; ) {
      foreach (i; 0 .. (n >> 1) / l) {
        const(long) g = gs[i];
        foreach (j; (i << 1) * l .. (i << 1 | 1) * l) {
          const t = cast(int)((g * xs[j + l]) % M);
          if ((xs[j + l] = xs[j] - t) < 0) xs[j + l] += M;
          if ((xs[j] += t) >= M) xs[j] -= M;
        }
      }
    }
  }
  void invFft(int[] xs) const {
    const n = cast(int)(xs.length);
    assert(!(n & (n - 1)), "Fft.invFft: |xs| must be a power of two");
    assert(n <= 1 << K, "Fft.invFft: |xs| <= 2^K must hold");
    for (int l = 1; l < n; l <<= 1) reverse(xs[l .. l << 1]);
    for (int l = 1; l < n; l <<= 1) {
      foreach (i; 0 .. (n >> 1) / l) {
        const(long) g = gs[i];
        foreach (j; (i << 1) * l .. (i << 1 | 1) * l) {
          int t = cast(int)((g * (xs[j] - xs[j + l])) % M);
          if (t < 0) t += M;
          if ((xs[j] += xs[j + l]) >= M) xs[j] -= M;
          xs[j + l] = t;
        }
      }
    }
  }
  T[] convolute(T)(inout(T)[] as, inout(T)[] bs) const if (isIntegral!T) {
    const na = cast(int)(as.length), nb = cast(int)(bs.length);
    int n, invN = 1;
    for (n = 1; n < na + nb - 1; n <<= 1) {
      invN = ((invN & 1) ? (invN + M) : invN) >> 1;
    }
    auto xs = new int[n], ys = new int[n];
    foreach (i; 0 .. na) if ((xs[i] = cast(int)(as[i] % M)) < 0) xs[i] += M;
    foreach (i; 0 .. nb) if ((ys[i] = cast(int)(bs[i] % M)) < 0) ys[i] += M;
    fft(xs);
    fft(ys);
    foreach (i; 0 .. n) {
      xs[i] = cast(int)((((cast(long)(xs[i]) * ys[i]) % M) * invN) % M);
    }
    invFft(xs);
    auto cs = new T[na + nb - 1];
    foreach (i; 0 .. na + nb - 1) cs[i] = cast(T)(xs[i]);
    return cs;
  }
  ModInt!M[] convolute(inout(ModInt!M)[] as, inout(ModInt!M)[] bs) const {
    const na = cast(int)(as.length), nb = cast(int)(bs.length);
    int n, invN = 1;
    for (n = 1; n < na + nb - 1; n <<= 1) {
      invN = ((invN & 1) ? (invN + M) : invN) >> 1;
    }
    auto xs = new int[n], ys = new int[n];
    foreach (i; 0 .. na) xs[i] = as[i].x;
    foreach (i; 0 .. nb) ys[i] = bs[i].x;
    fft(xs);
    fft(ys);
    foreach (i; 0 .. n) {
      xs[i] = cast(int)((((cast(long)(xs[i]) * ys[i]) % M) * invN) % M);
    }
    invFft(xs);
    auto cs = new ModInt!M[na + nb - 1];
    foreach (i; 0 .. na + nb - 1) cs[i].x = xs[i];
    return cs;
  }
  int[] convolute(int M1)(inout(ModInt!M1)[] as, inout(ModInt!M1)[] bs) const
      if (M != M1) {
    const na = cast(int)(as.length), nb = cast(int)(bs.length);
    int n, invN = 1;
    for (n = 1; n < na + nb - 1; n <<= 1) {
      invN = ((invN & 1) ? (invN + M) : invN) >> 1;
    }
    auto xs = new int[n], ys = new int[n];
    foreach (i; 0 .. na) xs[i] = as[i].x;
    foreach (i; 0 .. nb) ys[i] = bs[i].x;
    fft(xs);
    fft(ys);
    foreach (i; 0 .. n) {
      xs[i] = cast(int)((((cast(long)(xs[i]) * ys[i]) % M) * invN) % M);
    }
    invFft(xs);
    return xs[0 .. na + nb - 1];
  }
}

alias Fft0 = Fft!(998244353, 3, 20);


void main() {
  prepare;
  const FFT = new Fft0;
  
  debug {
    enum LIM_SMALL = 50;
    auto brt = new Mint[4][][][][](LIM_SMALL, LIM_SMALL, LIM_SMALL, LIM_SMALL);
    brt[0][0][0][0][0] = 1;
    foreach (a; 0 .. LIM_SMALL) foreach (b; 0 .. LIM_SMALL) foreach (c; 0 .. LIM_SMALL) foreach (d; 0 .. LIM_SMALL) {
      if (a + 1 < LIM_SMALL) brt[a + 1][b][c][d][1] += brt[a][b][c][d][0];
      if (a + 1 < LIM_SMALL) brt[a + 1][b][c][d][0] += brt[a][b][c][d][1];
      if (b + 1 < LIM_SMALL) brt[a][b + 1][c][d][2] += brt[a][b][c][d][1];
      if (b + 1 < LIM_SMALL) brt[a][b + 1][c][d][1] += brt[a][b][c][d][2];
      if (c + 1 < LIM_SMALL) brt[a][b][c + 1][d][3] += brt[a][b][c][d][2];
      if (c + 1 < LIM_SMALL) brt[a][b][c + 1][d][2] += brt[a][b][c][d][3];
      if (d + 1 < LIM_SMALL) brt[a][b][c][d + 1][0] += brt[a][b][c][d][3];
      if (d + 1 < LIM_SMALL) brt[a][b][c][d + 1][3] += brt[a][b][c][d][0];
    }
  }
  
  try {
    for (; ; ) {
      const A = readInt();
      const B = readInt();
      const C = readInt();
      const D = readInt();
      
      const limAB = min(A, B) + 1;
      const limCD = min(C, D) + 1;
      auto fs = new Mint[limAB + 1];
      auto gs = new Mint[limCD + 1];
      foreach (j; 0 .. limAB + 1) {
        if (A - j >= 0 && (A - j) % 2 == 0 &&
            B - j >= 0 && (B - j) % 2 == 0) {
          fs[j] = invFac[(A - j) / 2] * invFac[j] * invFac[(B - j) / 2];
        }
      }
      foreach (j; 0 .. limCD + 1) {
        if (D - j >= 0 && (D - j) % 2 == 0 &&
            C - j >= 0 && (C - j) % 2 == 0) {
          gs[j] = invFac[(D - j) / 2] * invFac[j] * invFac[(C - j) / 2];
        }
      }
      const hs = FFT.convolute(fs, gs);
      Mint ans;
      foreach (s; 0 .. limAB + limCD + 1) {
        if (A + D - s >= 0 && (A + D - s) % 2 == 0 &&
            s % 2 == 0 &&
            B + C - s >= 0 && (B + C - s) % 2 == 0) {
          Mint prod = hs[s];
          prod *= fac[(A + D - s) / 2] * fac[s] * fac[(B + C - s) / 2];
          prod *= binom((A + D) / 2, s / 2);
          prod *= binom((B + C) / 2 - 1, s / 2 - 1);
          ans += prod;
        }
      }
      writeln(ans);
      
      debug {
        if (max(A, B, C, D) < LIM_SMALL) {
          writeln("brt = ", brt[A][B][C][D][0]);
          assert(ans == brt[A][B][C][D][0]);
        }
      }
    }
  } catch (EOFException e) {
  }
}

Submission Info

Submission Time
Task D - C4
User hos_lyric
Language D (LDC 1.20.1)
Score 1800
Code Size 10332 Byte
Status AC
Exec Time 176 ms
Memory 45068 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1800 / 1800
Status
AC × 3
AC × 45
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, example0.txt, example1.txt, example2.txt
Case Name Status Exec Time Memory
000.txt AC 176 ms 44772 KB
001.txt AC 170 ms 44904 KB
002.txt AC 169 ms 44708 KB
003.txt AC 171 ms 45068 KB
004.txt AC 170 ms 44792 KB
005.txt AC 169 ms 44924 KB
006.txt AC 172 ms 44956 KB
007.txt AC 174 ms 44696 KB
008.txt AC 174 ms 44680 KB
009.txt AC 175 ms 44900 KB
010.txt AC 168 ms 44992 KB
011.txt AC 167 ms 44816 KB
012.txt AC 175 ms 44696 KB
013.txt AC 171 ms 44768 KB
014.txt AC 173 ms 44780 KB
015.txt AC 170 ms 44920 KB
016.txt AC 173 ms 44808 KB
017.txt AC 173 ms 44808 KB
018.txt AC 171 ms 44864 KB
019.txt AC 172 ms 44792 KB
020.txt AC 166 ms 41452 KB
021.txt AC 113 ms 36144 KB
022.txt AC 110 ms 35260 KB
023.txt AC 85 ms 32872 KB
024.txt AC 114 ms 36296 KB
025.txt AC 114 ms 36832 KB
026.txt AC 112 ms 35944 KB
027.txt AC 113 ms 35964 KB
028.txt AC 85 ms 32888 KB
029.txt AC 83 ms 32828 KB
030.txt AC 109 ms 35644 KB
031.txt AC 164 ms 42032 KB
032.txt AC 84 ms 32400 KB
033.txt AC 166 ms 41340 KB
034.txt AC 109 ms 35252 KB
035.txt AC 110 ms 36216 KB
036.txt AC 86 ms 32144 KB
037.txt AC 79 ms 32564 KB
038.txt AC 84 ms 32680 KB
039.txt AC 85 ms 33052 KB
040.txt AC 171 ms 44752 KB
041.txt AC 164 ms 44688 KB
example0.txt AC 57 ms 29044 KB
example1.txt AC 61 ms 29048 KB
example2.txt AC 170 ms 44600 KB