QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#619987#2834. NonsenseemsgerRE 0ms0kbC++203.5kb2024-10-07 16:13:462024-10-07 16:13:51

Judging History

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

  • [2024-10-07 16:13:51]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-07 16:13:46]
  • 提交

answer

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;

void set_io(std::string name)
{
#ifndef NO_FREOPEN
  freopen((name + ".in").c_str(), "r", stdin);
  freopen((name + ".out").c_str(), "w", stdout);
#endif
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

template <u32 M>
struct static_modint
{
  u32 v;

  static_modint() : v(0) {}
  static_modint(i64 x) : v((x %= M) < 0 ? x + M : x) {}

  u32 val() const { return v; }

  using mint = static_modint;

  mint &operator+=(mint x)
  {
    if ((v += x.v) >= M) v -= M;
    return *this;
  }

  mint &operator-=(mint x)
  {
    if ((v += M - x.v) >= M) v -= M;
    return *this;
  }

  mint &operator*=(mint x)
  {
    v = (u64)v * x.v % M;
    return *this;
  }

  friend mint operator+(mint a, mint b) { return a += b; }
  friend mint operator-(mint a, mint b) { return a -= b; }
  friend mint operator*(mint a, mint b) { return a *= b; }

  mint pow(u64 x) const
  {
    mint res = 1;
    mint base = *this;
    while (x) {
      if (x & 1) res *= base;
      base *= base;
      x >>= 1;
    }
    return res;
  }

  mint inv() const
  {
    return pow(M - 2);
  }
};

using mint = static_modint<998'244'353>;

void solve_x_eq_y(int n, mint x, int maxa, int maxb, const std::vector<std::pair<int, int>> &q)
{
  int maxab = maxa + maxb + 1;
  std::vector<mint> decr(maxab + 1);
  decr[0] = 1;
  for (int i = 0; i < maxab; i++) decr[i + 1] = decr[i] * (n + 1 - i);

  std::vector<mint> fac(maxab + 1), ifac(maxab + 1);
  fac[0] = 1;
  for (int i = 1; i <= maxab; i++) fac[i] = fac[i - 1] * i;
  ifac[maxab] = fac[maxab].inv();
  for (int i = maxab; i >= 1; i--) ifac[i - 1] = ifac[i] * i;

  for (auto [a, b] : q) {
    std::cout << (decr[a + b + 1] * ifac[a + b + 1] * x.pow(n - a - b)).val() << std::endl;
  }
}

void solve_x_neq_y(int n, mint x, mint y, int maxa, int maxb, const std::vector<std::pair<int, int>> &q)
{
  std::vector f(maxa + 1, std::vector<mint>(maxb + 1));

  int maxab = maxa + maxb;
  std::vector<mint> decr(maxab + 1);
  decr[0] = 1;
  for (int i = 0; i < maxab; i++) decr[i + 1] = decr[i] * (n + 1 - i);

  std::vector<mint> fac(maxab + 1), ifac(maxab + 1);
  fac[0] = 1;
  for (int i = 1; i <= maxab; i++) fac[i] = fac[i - 1] * i;
  ifac[maxab] = fac[maxab].inv();
  for (int i = maxab; i >= 1; i--) ifac[i - 1] = ifac[i] * i;

  mint ixy = (x - y).inv();
  f[0][0] = (x.pow(n + 1) - y.pow(n + 1)) * ixy;
  for (int a = 1; a <= maxa; a++) f[a][0] = (decr[a] * ifac[a] * x.pow(n + 1 - a) - f[a - 1][0]) * ixy;
  for (int b = 1; b <= maxb; b++) f[0][b] = (f[0][b - 1] - decr[b] * ifac[b] * y.pow(n + 1 - b)) * ixy;
  for (int a = 1; a <= maxa; a++) {
    for (int b = 1; b <= maxb; b++) {
      f[a][b] = (f[a][b - 1] - f[a - 1][b]) * ixy;
    }
  }

  for (auto [a, b] : q) {
    std::cout << f[a][b].val() << std::endl;
  }
}

int main()
{
  set_io("count");

  int n, x, y, m;
  while (std::cin >> n >> x >> y >> m) {

    std::vector<std::pair<int, int>> q;
    int maxa = 0, maxb = 0;
    for (int i = 0; i < m; i++) {
      int a, b;
      std::cin >> a >> b;
      maxa = std::max(maxa, a);
      maxb = std::max(maxb, b);
      q.emplace_back(a, b);
    }

    if (x == y) {
      solve_x_eq_y(n, x, maxa, maxb, q);
    } else {
      solve_x_neq_y(n, x, y, maxa, maxb, q);
    }
  }
}

详细

Test #1:

score: 0
Dangerous Syscalls

input:

3 1 2 2
1 1
1 2
100 2 3 1
1 1

output:


result: