QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209985#61. Cut Cut Cut!NeroWA 1ms3776kbC++2010.5kb2023-10-10 21:08:352023-10-10 21:08:36

Judging History

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

  • [2023-10-10 21:08:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3776kb
  • [2023-10-10 21:08:35]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef ALGO
#include "el_psy_congroo.hpp"
#else
#define CHECK(...)
#define DUMP(...)
#endif

using LL = long long;
template<typename T, typename U>
inline bool enlarge(T& a, U b) { return a < b ? (a = b, true) : false; }
template<typename T, typename U>
inline bool minify(T& a, U b) { return a > b ? (a = b, true) : false; }





namespace power_details {
template<typename T, typename Enable = void>
struct Identity { static constexpr T get() { return T{1}; } };
template<typename T>
struct Identity<T, std::void_t<decltype(T::identity())>> {
  static constexpr T get() { return T::identity(); }
};
}  // namespace power_details

template<typename T,
         typename MulFunc = std::function<T(T,T)>,
         typename SqrFunc = std::function<T(T)>>
constexpr T power(T a, long long b, MulFunc&& mul, SqrFunc&& sqr) {
  T ret = sqr(power_details::Identity<T>::get());
  for (; b; b >>= 1, a = sqr(a)) if (b & 1) ret = mul(ret, a);
  return ret;
}
template<typename T, typename MulFunc = std::function<T(T,T)>>
constexpr T power(T a, long long b, MulFunc&& mul) {
  return power(a, b, std::forward<MulFunc>(mul), [&](T x) { return mul(x, x); });
}
template<typename T, typename IT = T>
constexpr T power(T a, long long b, T mod) {
  return power(a, b, [&mod](T x, T y) { return static_cast<IT>(x) * y % mod; });
}
template<typename T>
constexpr T power(T a, long long b) {
  return power(a, b, [](T x, T y) { return x * y; });
}

template<typename T>
struct PowerTable final : public std::vector<T> {
  PowerTable() = default;
  PowerTable(int n, const T& g)
    : PowerTable(n, g, [](const T& lhs, const T& rhs) -> T { return lhs * rhs; }) {}
  template<typename MulFunc = std::function<T(T,T)>>
  PowerTable(int n, const T& g, MulFunc&& mul) {
    static_assert(sizeof(PowerTable) == sizeof(std::vector<T>), "");
    this->resize(n + 1);
    this->at(0) = power_details::Identity<T>::get();
    for (int i = 1; i < this->size(); ++i) this->at(i) = mul(this->at(i - 1), g);
  }
};

//-#include "power.hpp"


template<typename Kernel>
class ModWrapper {
 public:
  static constexpr int get_mod() { return Kernel::get_mod(); }
  static void set_mod(int m) { Kernel::set_mod(m); }

  // Implicit conversion is allowed.
  template<typename T> requires std::is_integral_v<T> && (sizeof(T) >= 4)
  ModWrapper(T v) : v_(wrap(norm(v))) {}
  template<typename T> requires std::is_integral_v<T> && (sizeof(T) < 4)
  ModWrapper(T v) : v_(wrap(norm(static_cast<int>(v)))) {}

  ModWrapper() = default;
  ~ModWrapper() = default;

  // Explicit conversion to other type.
  template<typename T>
  explicit operator T() const {
    if constexpr(std::is_same<T, bool>::value && requires () { static_cast<T>(v_); }) {
      return static_cast<T>(v_);
    } else {
      return static_cast<T>(unwrap(v_));
    }
  }

  int val() const { return unwrap(v_); }
  ModWrapper& operator+=(const ModWrapper& rhs) { Kernel::add(v_, rhs.v_); return *this; }
  ModWrapper& operator-=(const ModWrapper& rhs) { Kernel::sub(v_, rhs.v_); return *this; }
  ModWrapper& operator*=(const ModWrapper& rhs) { Kernel::mul(v_, rhs.v_); return *this; }
  ModWrapper& operator/=(const ModWrapper& rhs) { Kernel::mul(v_, rhs.inv().v_); return *this; }
  ModWrapper operator+(const ModWrapper& rhs) const { ModWrapper ret = *this; return ret += rhs; }
  ModWrapper operator-(const ModWrapper& rhs) const { ModWrapper ret = *this; return ret -= rhs; }
  ModWrapper operator*(const ModWrapper& rhs) const { ModWrapper ret = *this; return ret *= rhs; }
  ModWrapper operator/(const ModWrapper& rhs) const { ModWrapper ret = *this; return ret /= rhs; }
  bool operator==(const ModWrapper& rhs) const { return val() == rhs.val(); }
  bool operator!=(const ModWrapper& rhs) const { return !(*this == rhs); }
  const ModWrapper operator-() const { ModWrapper ret{0}; Kernel::sub(ret.v_, v_); return ret; }
  const ModWrapper& operator++() { Kernel::add(v_, ModWrapper{1}.v_); return *this; }
  const ModWrapper operator++(int) { ModWrapper ret = *this; ++(*this); return ret; }
  const ModWrapper& operator--() { Kernel::sub(v_, ModWrapper{1}.v_); return *this; }
  const ModWrapper operator--(int) { ModWrapper ret = *this; --(*this); return ret; }

  ModWrapper power(long long b) const { return ::power(*this, b); }
  ModWrapper inv() const {
    if constexpr(requires (StorageType x) { Kernel::inv(x); }) {
      ModWrapper ret = *this;
      Kernel::inv(ret.v_);
      return ret;
    } else {
      return power(Kernel::get_mod() - 2);
    }
  }

  std::string to_string() const { return std::string("{") + std::to_string(val()) + "}"; }

 private:
  using StorageType = typename Kernel::StorageType;

  template<typename T>
  static T norm(T v) {
    const int MOD = Kernel::get_mod();
    if constexpr(sizeof(T) > sizeof(MOD)) {
      v %= MOD;
      if (v < 0) v += MOD;
    } else {
      if (v >= MOD) v -= MOD;
      if (v < 0) v += MOD;
      if (v >= MOD || v < 0) {
        v %= MOD;
        if (v < 0) v += MOD;
      }
    }
    return v;
  }

  static constexpr StorageType wrap(int x) {
    if constexpr(requires () { Kernel::wrap(x); }) {
      return Kernel::wrap(x);
    } else {
      return static_cast<StorageType>(x);
    }
  }

  static constexpr int unwrap(StorageType x) {
    if constexpr(requires () { Kernel::unwrap(x); }) {
      return Kernel::unwrap(x);
    } else {
      return static_cast<int>(x);
    }
  }

  StorageType v_{};
};

template<typename Kernel>
std::string to_string(const ModWrapper<Kernel>& v) {
  return v.to_string();
}

//-#include "mod_wrapper.hpp"


namespace integral_details {

template<int MOD>
struct IntegralKernel {
  using StorageType = int;
  static constexpr void add(int& x, int y) { if ((x += y) >= MOD) x -= MOD; }
  static constexpr void sub(int& x, int y) { if ((x += MOD - y) >= MOD) x -= MOD; }
  static constexpr void mul(int& x, int y) { x = static_cast<int64_t>(x) * y % MOD; }
  static constexpr int get_mod() { return MOD; }
};

}  // namespace integral_details

template<int MOD>
using Integral = ModWrapper<integral_details::IntegralKernel<MOD>>;

const int MOD = 998244353;
using Mint = Integral<MOD>;

//-#include "mod.hpp"



template<typename T>
struct Polynomial final : public std::vector<T> {
  using std::vector<T>::vector;

  int size() const { return std::vector<T>::size(); }
  int deg() const { return size() - 1; }  // Here we use -1 to represent -\infty.
  T get(int pos) const { return pos >= 0 && pos < size() ? (*this)[pos] : T{}; }
  T& touch(int pos) { if (pos >= size()) std::vector<T>::resize(pos + 1, T{}); return (*this)[pos]; }
  T eval(T a) const {
    T ret{};
    for (int i = deg(); i >= 0; --i) ret = ret * a + (*this)[i];
    return ret;
  }
};

template<typename T>
void norm(Polynomial<T>& p) { while (!p.empty() && p.back() == T{}) p.pop_back(); }

template<typename T>
Polynomial<T>& operator+=(Polynomial<T>& lhs, const Polynomial<T>& rhs) {
  lhs.resize(std::max(lhs.size(), rhs.size()), T{});
  for (int i = 0; i < rhs.size(); ++i) lhs[i] += rhs[i];
  norm(lhs);
  return lhs;
}
template<typename T>
Polynomial<T> operator+(Polynomial<T> lhs, const Polynomial<T>& rhs) { return lhs += rhs; }

template<typename T>
Polynomial<T>& operator-=(Polynomial<T>& lhs, const Polynomial<T>& rhs) {
  lhs.resize(std::max(lhs.size(), rhs.size()), T{});
  for (int i = 0; i < rhs.size(); ++i) lhs[i] -= rhs[i];
  norm(lhs);
  return lhs;
}
template<typename T>
Polynomial<T> operator-(Polynomial<T> lhs, const Polynomial<T>& rhs) { return lhs -= rhs; }

template<typename T>
Polynomial<T>& operator*=(Polynomial<T>& p, T a) {
  for (int i = 0; i < p.size(); ++i) p[i] *= a;
  norm(p);
  return p;
}
template<typename T>
Polynomial<T> operator*(T a, Polynomial<T> p) { return p *= a; }
template<typename T>
Polynomial<T> operator*(const Polynomial<T>& p, T a) { return a * p; }

template<typename T>
Polynomial<T> mod_len(Polynomial<T> poly, int len) {
  // poly % x^len
  if (poly.size() > len) poly.resize(len);
  norm(poly);
  return poly;
}

template<typename T>
Polynomial<T> enforce_len(Polynomial<T> poly, int len) { poly.resize(len, T{}); return poly; }

template<typename T>
T eval(const Polynomial<T>& poly, T a) {  // Returns Poly(a).
  return poly.eval(a);
  // NOTE: It equals to (poly % Polynomial<T>{-a, 1}).get(0), if '%' presents.
}

template<typename T>
Polynomial<T> derivate(Polynomial<T> poly) {
  if (poly.size() <= 1) return Polynomial<T>{};
  for (int i = 1; i < poly.size(); ++i) poly[i - 1] = poly[i] * i;
  poly.pop_back();
  norm(poly);
  return poly;
}

template<typename T>
Polynomial<T> integrate(Polynomial<T> poly) {
  if (poly.deg() < 0) return poly;
  poly.emplace_back();
  for (int i = (int)poly.size() - 1; i > 0; --i) poly[i] = poly[i - 1] / i;
  poly[0] = T{};
  norm(poly);
  return poly;
}

template<typename T>
Polynomial<T> naive_mul(const Polynomial<T>& lhs, const Polynomial<T>& rhs) {
  Polynomial<T> ret{};
  for (int i = 0; i < lhs.size(); ++i) {
    for (int j = 0; j < rhs.size(); ++j) {
      ret.touch(i + j) += lhs.get(i) * rhs.get(j);
    }
  }
  norm(ret);
  return ret;
}

//-#include "poly_common.hpp"

std::mt19937 rng(clock());

int random(int l, int r) {
  return rng() % (r - l + 1) + l;
}

using Poly = Polynomial<Mint>;

struct Edge {
  int v;
};

struct Space {
  std::vector<Poly> space;
  Poly sum{};

  Space() {}

  void take(Poly v) {
    sum += v * Mint{random(1, MOD - 1)};
    for (int i = 0; i < space.size(); ++i) {
      int z = (int)space[i].size() - 1;
      assert(space[i][z] == 1);
      if (v.get(z)) v -= space[i] * v[z];
    }
    norm(v);
    if (v.empty()) return;
    if (v.back() != 1) v *= Mint{1} / v.back();
    for (auto& w : space) if (w.get((int)v.size() - 1)) {
      w -= v * w[(int)v.size() - 1];
    }
    space.emplace_back(v);
  }

  int rank() const { return space.size(); }
};

struct Solver {

  void solve(int ca, std::istream& reader) {
    int N, M;
    reader >> N >> M;
    std::vector<std::vector<Edge>> graph(N);
    for (int i = 0; i < M; ++i) {
      int x, y;
      reader >> x >> y; --x; --y;
      graph[x].emplace_back(Edge{.v = y});
    }
    std::vector<Space> spaces(N);
    int D = graph[0].size();
    for (int i = 0; i < D; ++i) {
      Poly tmp;
      tmp.touch(i) = 1;
      spaces[graph[0][i].v].take(tmp);
    }
    for (int u = 1; u < N; ++u) {
      printf("%d%c", spaces[u].rank(), " \n"[u + 1 == N]);
      for (auto e : graph[u]) {
        spaces[e.v].take(spaces[u].sum);
      }
    }
  }
};

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;

  int cas = 1;
  // reader >> cas;
  for (int ca = 1; ca <= cas; ++ca) {
    auto solver = std::make_unique<Solver>();
    solver->solve(ca, reader);
  }
}


详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3692kb

input:

3 3
1 2
1 3
2 3

output:

1 2

result:

ok 2 number(s): "1 2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

8 8
1 2
1 3
1 5
2 4
2 5
3 6
4 5
7 8

output:

1 1 1 2 1 0 0

result:

ok 7 numbers

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3708kb

input:

20 70
3 18
14 16
8 10
5 7
2 14
10 18
14 15
17 19
18 20
4 6
3 20
16 17
6 7
6 17
6 19
5 19
12 16
18 19
13 19
13 19
8 9
15 17
8 9
1 7
5 18
6 14
2 17
4 20
12 16
9 20
2 7
6 19
12 13
6 7
1 5
19 20
9 14
13 14
16 17
17 20
9 16
1 6
12 15
2 8
1 3
4 19
1 4
9 13
14 15
15 20
17 18
14 19
13 14
2 5
7 14
7 18
10 16...

output:

0 1 1 1 2 3 0 1 0 0 1 2 4 2 3 3 6 5 6

result:

wrong answer 6th numbers differ - expected: '4', found: '3'