QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#438768#8792. Candieshos_lyricAC ✓4966ms5972kbC++146.5kb2024-06-11 05:00:332024-06-11 05:00:33

Judging History

你现在查看的是最新测评结果

  • [2024-06-11 05:00:33]
  • 评测
  • 测评结果:AC
  • 用时:4966ms
  • 内存:5972kb
  • [2024-06-11 05:00:33]
  • 提交

answer

#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 <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#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> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
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; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
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; }
};
////////////////////////////////////////////////////////////////////////////////

constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;

constexpr int LIM_INV = 100'010;
Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV];

void prepare() {
  inv[1] = 1;
  for (int i = 2; i < LIM_INV; ++i) {
    inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
  }
  fac[0] = invFac[0] = 1;
  for (int i = 1; i < LIM_INV; ++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_INV);
      return fac[n] * invFac[k] * invFac[n - k];
    } else {
      return 0;
    }
  }
}


Mint two[LIM_INV], invTwo[LIM_INV];

/*
  W = x (2 + W^3)
  [x^n] W^k
*/
Mint WW(int k, int n) {
  assert(k >= -1);
  if (n == 0) return (k == 0) ? 1 : 0;
  if (n < k) return 0;
  if ((n - k) % 3 != 0) return 0;
  const int m = n - (n - k) / 3;
  return k * ((n < 0) ? -inv[-n] : inv[n]) * binom(n, m) * ((m < 0) ? invTwo[-m] : two[m]);
}

Mint solve(int A, int B, int C) {
  // binom(1/2, h) (-1)^h
  vector<Mint> bns(3 * A + 10);
  bns[0] = 1;
  for (int i = 0; i + 1 < (int)bns.size(); ++i) {
    bns[i + 1] = bns[i] * -(inv[2] - i) * inv[1 + i];
  }
  
  Mint ans = 0;
  for (int phase = 0; phase < 2; ++phase) {
    const int N = A + B + C;
    const int L = A - B;
    const int M = A - C;
    for (int i = 0; i <= N + 1; ++i) {
      // t^i x^(d+2f-(i+1)) y^(e+2f-(i+1))
      for (int f = 0; f <= i && 2*f <= M + (i+1); ++f) {
        const int e = M + (i+1) - 2*f;
        const int d = i - e - f;
        if (d >= 0) {
          const int n = N - i;
          const int l = L - (d + 2*f - (i+1));
          Mint sum = 0;
          // bn x^h W^(2h-1)
          {
            const int h = l;
            if (h >= 0) sum += bns[h] * WW(2*h - 1, n);
          }
          // bn x^(h-1) W^(2h)
          {
            const int h = l + 1;
            if (h >= 0) sum -= bns[h] * WW(2*h, n);
          }
          if (sum) {
            ans += (fac[i] * invFac[d] * invFac[e] * invFac[f]) * sum;
          }
        }
      }
    }
    swap(B, C);
  }
  return ans;
}

int main() {
  prepare();
  two[0] = 1;
  invTwo[0] = 1;
  for (int i = 1; i < LIM_INV; ++i) {
    two[i] = two[i - 1] * 2;
    invTwo[i] = invTwo[i - 1] * inv[2];
  }
// for(int k=-1;k<=4;++k){cerr<<"W^"<<k<<" = ";for(int n=-1;n<=20;++n)cerr<<WW(k,n)<<" ";cerr<<endl;}
  
  int A, B, C;
// A=3;for(B=0;B<=3;++B)for(int C=0;C<=3;++C){const Mint res=solve(A,B,C);cerr<<A<<" "<<B<<" "<<C<<": "<<res<<endl;}
  for (; ~scanf("%d%d%d", &A, &B, &C); ) {
    const Mint ans = solve(A, B, C);
    printf("%u\n", ans.x);
  }
  return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5740kb

input:

4 3 2

output:

368

result:

ok answer is '368'

Test #2:

score: 0
Accepted
time: 4966ms
memory: 5860kb

input:

10000 10000 10000

output:

905642282

result:

ok answer is '905642282'

Test #3:

score: 0
Accepted
time: 3ms
memory: 5736kb

input:

99 99 99

output:

604759627

result:

ok answer is '604759627'

Test #4:

score: 0
Accepted
time: 3346ms
memory: 5816kb

input:

10000 9876 6543

output:

172894229

result:

ok answer is '172894229'

Test #5:

score: 0
Accepted
time: 2ms
memory: 5704kb

input:

7 1 6

output:

5577

result:

ok answer is '5577'

Test #6:

score: 0
Accepted
time: 0ms
memory: 5788kb

input:

28 23 17

output:

816429586

result:

ok answer is '816429586'

Test #7:

score: 0
Accepted
time: 2ms
memory: 5824kb

input:

87 54 22

output:

401507657

result:

ok answer is '401507657'

Test #8:

score: 0
Accepted
time: 2ms
memory: 5704kb

input:

50 40 16

output:

770938562

result:

ok answer is '770938562'

Test #9:

score: 0
Accepted
time: 2ms
memory: 5824kb

input:

72 19 53

output:

607733148

result:

ok answer is '607733148'

Test #10:

score: 0
Accepted
time: 2ms
memory: 5900kb

input:

8 4 4

output:

325590

result:

ok answer is '325590'

Test #11:

score: 0
Accepted
time: 2ms
memory: 5700kb

input:

65 45 14

output:

452076388

result:

ok answer is '452076388'

Test #12:

score: 0
Accepted
time: 2ms
memory: 5824kb

input:

82 8 67

output:

708832480

result:

ok answer is '708832480'

Test #13:

score: 0
Accepted
time: 0ms
memory: 5700kb

input:

65 10 35

output:

769016918

result:

ok answer is '769016918'

Test #14:

score: 0
Accepted
time: 2ms
memory: 5700kb

input:

4 3 4

output:

1408

result:

ok answer is '1408'

Test #15:

score: 0
Accepted
time: 446ms
memory: 5916kb

input:

9139 6356 279

output:

833879698

result:

ok answer is '833879698'

Test #16:

score: 0
Accepted
time: 253ms
memory: 5936kb

input:

3888 2407 1937

output:

380556889

result:

ok answer is '380556889'

Test #17:

score: 0
Accepted
time: 1494ms
memory: 5928kb

input:

9161 3171 7913

output:

643956900

result:

ok answer is '643956900'

Test #18:

score: 0
Accepted
time: 68ms
memory: 5712kb

input:

1392 1354 938

output:

491399135

result:

ok answer is '491399135'

Test #19:

score: 0
Accepted
time: 80ms
memory: 5888kb

input:

5930 427 1403

output:

786969030

result:

ok answer is '786969030'

Test #20:

score: 0
Accepted
time: 3ms
memory: 5896kb

input:

507 99 150

output:

960656496

result:

ok answer is '960656496'

Test #21:

score: 0
Accepted
time: 326ms
memory: 5776kb

input:

3119 2372 2681

output:

751161512

result:

ok answer is '751161512'

Test #22:

score: 0
Accepted
time: 584ms
memory: 5972kb

input:

6636 3688 2743

output:

839083240

result:

ok answer is '839083240'

Test #23:

score: 0
Accepted
time: 140ms
memory: 5860kb

input:

4890 475 2865

output:

788640273

result:

ok answer is '788640273'

Test #24:

score: 0
Accepted
time: 485ms
memory: 5776kb

input:

6708 663 6384

output:

426276232

result:

ok answer is '426276232'

Test #25:

score: 0
Accepted
time: 2ms
memory: 5816kb

input:

1 1 1

output:

2

result:

ok answer is '2'

Extra Test:

score: 0
Extra Test Passed