QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#209985 | #61. Cut Cut Cut! | Nero | WA | 1ms | 3776kb | C++20 | 10.5kb | 2023-10-10 21:08:35 | 2023-10-10 21:08:36 |
Judging History
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'