QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722572 | #9608. 皮鞋的多项式 | TheZone | 3 | 44ms | 22192kb | C++20 | 19.0kb | 2024-11-07 19:35:22 | 2024-11-07 19:35:23 |
Judging History
answer
#pragma GCC optimize(3, "unroll-loops", "no-stack-protector")
#define atsum(l, r) accumulate(l, r, 0)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
template <typename T>
inline void chkmin(T &x, T y) { x = min(x, y); }
template <typename T>
inline void chkmax(T &x, T y) { x = max(x, y); }
namespace FastIO
{
// ------------------------------
#define IN_HAS_NEG
#define OUT_HAS_NEG
#define CHK_EOF
#define DISABLE_MMAP
// ------------------------------
#if __cplusplus < 201400
#error Please use C++14 or higher.
#endif
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if ( defined(LOCAL) || defined (_WIN32) ) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include<sys/mman.h>
#endif
#ifdef LOCAL
inline char gc() { return getchar(); }
inline void pc(char c) { putchar(c); }
#else
#ifdef DISABLE_MMAP
INLINE_V constexpr int _READ_SIZE = 1 << 18;
INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char gc()
{
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) )
{
_read_ptr = _read_buffer;
_read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin);
#ifdef CHK_EOF
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF;
#endif
}
return *_read_ptr++;
}
#else
INLINE_V static const char *_read_ptr = (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0);
inline char gc() { return *_read_ptr++; }
#endif
INLINE_V constexpr int _WRITE_SIZE = 1 << 18;
INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer;
inline void pc(char c)
{
*_write_ptr++ = c;
if ( __builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false) )
{
fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout);
_write_ptr = _write_buffer;
}
}
INLINE_V struct _auto_flush
{
~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); }
} _auto_flush;
#endif
#ifdef CHK_EOF
inline bool _isdigit(char c) { return ( c & 16 ) && c != EOF; }
inline bool _isgraph(char c) { return c > 32 && c != EOF; }
#else
inline bool _isdigit(char c) { return c & 16; }
inline bool _isgraph(char c) { return c > 32; }
#endif
template < class T >
INLINE_V constexpr bool _is_integer = numeric_limits < T >::is_integer;
template < class T >
INLINE_V constexpr bool _is_signed = numeric_limits < T >::is_signed;
template < class T >
INLINE_V constexpr bool _is_unsigned = _is_integer < T > && !_is_signed < T >;
template <> INLINE_V constexpr bool _is_integer < __int128 > = true;
template <> INLINE_V constexpr bool _is_integer < __uint128_t > = true;
template <> INLINE_V constexpr bool _is_signed < __int128 > = true;
template <> INLINE_V constexpr bool _is_unsigned < __uint128_t > = true;
#undef INLINE_V
inline void read(char &c) { do c = gc(); while ( !_isgraph(c) ); }
inline void read_cstr(char *s)
{
char c = gc(); while ( !_isgraph(c) ) c = gc();
while ( _isgraph(c) ) *s++ = c, c = gc();
*s = 0;
}
inline void read(string &s)
{
char c = gc(); s.clear(); while ( !_isgraph(c) ) c = gc();
while ( _isgraph(c) ) s.push_back(c), c = gc();
}
#ifdef IN_HAS_NEG
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void read(T &x)
{
char c = gc(); bool f = true; x = 0;
while ( !_isdigit(c) ) { if ( c == 45 ) f = false; c = gc(); }
if ( f ) while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
else while ( _isdigit(c) ) x = x * 10 - ( c & 15 ), c = gc();
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
inline void read(T &x)
{
char c = gc(); while ( !_isdigit(c) ) c = gc();
x = 0; while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
}
inline void write(char c) { pc(c); }
inline void write_cstr(const char *s) { while ( *s ) pc(*s++); }
inline void write(const string &s) { for ( char c : s ) pc(c); }
#ifdef OUT_HAS_NEG
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
if ( x >= 0 ) do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
else { pc(45); do buffer[digits++] = -( x % 10 ) | 48, x /= 10; while ( x ); }
while ( digits ) pc(buffer[--digits]);
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
while ( digits ) pc(buffer[--digits]);
}
template < int N > struct _tuple_io_helper
{
template < class ...T >
static inline void _read(tuple < T... > &x)
{ _tuple_io_helper < N - 1 >::_read(x), read(get < N - 1 > (x)); }
template < class ...T >
static inline void _write(const tuple < T... > &x)
{ _tuple_io_helper < N - 1 >::_write(x), pc(32), write(get < N - 1 > (x)); }
};
template <> struct _tuple_io_helper < 1 >
{
template < class ...T >
static inline void _read(tuple < T... > &x) { read(get < 0 > (x)); }
template < class ...T >
static inline void _write(const tuple < T... > &x) { write(get < 0 > (x)); }
};
template < class ...T >
inline void read(tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_read(x); }
template < class ...T >
inline void write(const tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_write(x); }
template < class T1, class T2 >
inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); }
template < class T1, class T2 >
inline void write(const pair < T1, T2 > &x) { write(x.first), pc(32), write(x.second); }
template < class T1, class ...T2 >
inline void read(T1 &x, T2 &...y) { read(x), read(y...); }
template < class ...T >
inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template < class T1, class ...T2 >
inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); }
template < class ...T >
inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template < class T >
inline void print(const T &x) { write(x); }
inline void print_cstr(const char *x) { write_cstr(x); }
template < class T1, class ...T2 >
inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
template < class ...T >
inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); }
inline void println() { pc(10); }
inline void println_cstr() { pc(10); }
template < class ...T >
inline void println(const T &...x) { print(x...), pc(10); }
template < class ...T >
inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); }
}
using namespace FastIO;
template <typename T>
inline void clear(T &x) {
T y;
swap(x, y);
}
template <uint32_t mod = 998244353>
class Modint {
private:
static constexpr uint32_t get_r() {
uint32_t ret = mod;
for (int i = 0; i < 4; i++) ret *= 2 - mod * ret;
return ret;
}
static constexpr uint32_t r = get_r();
static constexpr uint32_t n2 = -uint64_t(mod) % mod;
static_assert(r * mod == 1 && mod < (1 << 30) && mod & 1);
uint32_t data;
public:
constexpr Modint() : data(0) {}
template <class int_t>
constexpr Modint(const int_t x)
: data(reduce(
uint64_t((sizeof(int_t) < sizeof(uint32_t) ? x : x % int_t(mod)) +
mod) *
n2)){};
static constexpr uint32_t reduce(const uint64_t x) {
return (x + uint64_t(uint32_t(x) * (-r)) * mod) >> 32;
}
constexpr Modint &operator+=(const Modint &r) {
if (int32_t(data += r.data - 2 * mod) < 0) {
data += 2 * mod;
}
return *this;
}
constexpr Modint &operator-=(const Modint &r) {
if (int32_t(data -= r.data) < 0) {
data += 2 * mod;
}
return *this;
}
constexpr Modint &operator*=(const Modint &r) {
return data = reduce((uint64_t)data * r.data), *this;
}
constexpr Modint &operator/=(const Modint &r) { return *this *= r.inv(); }
constexpr friend Modint operator+(Modint l, const Modint &r) {
return l += r;
}
constexpr friend Modint operator-(Modint l, const Modint &r) {
return l -= r;
}
constexpr friend Modint operator*(Modint l, const Modint &r) {
return l *= r;
}
constexpr friend Modint operator/(Modint l, const Modint &r) {
return l /= r;
}
constexpr friend bool operator==(Modint l, const Modint &r) {
return l.value() == r.value();
}
constexpr Modint operator-() const { return Modint() - Modint(*this); }
template <class int_t>
constexpr Modint pow(int_t r) const {
Modint res(1), w(*this);
for (; r; r >>= 1, w *= w)
if (r & 1) res *= w;
return res;
}
constexpr Modint inv() const { return pow(mod - 2); }
constexpr uint32_t value() const {
uint32_t res = reduce(data);
return res >= mod ? res - mod : res;
}
};
using modint = Modint<>;
vector<modint> wn[22], iwn[22];
const modint inv2 = modint(2).inv();
struct Poly {
vector<modint> vec;
inline modint operator[](int x) const {
return 0 <= x && x < vec.size() ? vec[x] : 0;
}
inline Poly() {}
inline Poly(const vector<modint> &x) : vec(x) {}
inline Poly(const initializer_list<modint> &x) : vec(x) {}
inline bool empty() const { return vec.empty(); }
inline int size() const { return (int)vec.size(); }
inline void resize(int x) { vec.resize(x); }
inline auto begin() { return vec.begin(); }
inline auto end() { return vec.end(); }
inline auto begin() const { return vec.begin(); }
inline auto end() const { return vec.end(); }
inline bool empty() { return vec.empty(); }
inline modint &operator[](int x) { return vec[x]; }
inline Poly divxk(int x) const {
return Poly(vector<modint>(vec.begin() + min(x, size()), vec.end()));
}
inline Poly modxk(int x) const {
return Poly(vector<modint>(vec.begin(), vec.begin() + min(x, size())));
}
inline int size() { return vec.size(); }
inline static void NTT(Poly &c, int len, int type) {
if (len == 0) return;
vector<int> rev;
rev.resize(1 << len);
for (int i = 0; i < (1 << len); i++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << len - 1);
for (int i = 0; i < (1 << len); i++) {
if (rev[i] < i) swap(c[i], c[rev[i]]);
}
for (int i = 0; i < len; i++) {
if (!wn[i].size()) {
modint k = modint(3).pow((998244353 - 1) / (2 << i));
wn[i].resize(1 << i);
wn[i][0] = 1;
for (int j = 1; j < (1 << i); j++) wn[i][j] = wn[i][j - 1] * k;
}
if (!iwn[i].size()) {
modint k = modint(3).pow((998244353 - 1) / (2 << i));
k = k.inv();
iwn[i].resize(1 << i);
iwn[i][0] = 1;
for (int j = 1; j < (1 << i); j++)
iwn[i][j] = iwn[i][j - 1] * k;
}
if (type == 1)
for (int j = 0; j < (1 << len); j += 2 << i) {
#pragma GCC unroll 8
for (int k = 0; k < (1 << i); k++) {
modint a = c[j + k], b = c[j + (1 << i) + k] * wn[i][k];
c[j + k] = (a + b);
c[j + (1 << i) + k] = (a - b);
}
}
else
for (int j = 0; j < (1 << len); j += 2 << i) {
#pragma GCC unroll 8
for (int k = 0; k < (1 << i); k++) {
modint a = c[j + k],
b = c[j + (1 << i) + k] * iwn[i][k];
c[j + k] = (a + b);
c[j + (1 << i) + k] = (a - b);
}
}
}
if (type == -1) {
modint inv = inv2.pow(len);
for (int j = 0; j < (1 << len); j++) c[j] *= inv;
}
}
inline friend Poly operator*(Poly a, Poly b) {
if (!a.size() || !b.size()) return Poly{};
int len = a.size() + b.size() - 1;
int qwq = 0;
while ((1 << qwq) < len) qwq++;
a.resize(1 << qwq), b.resize(1 << qwq);
NTT(a, qwq, 1), NTT(b, qwq, 1);
for (int i = 0; i < (1 << qwq); i++) a[i] *= b[i];
NTT(a, qwq, -1);
return a.modxk(len);
}
inline friend Poly operator*(Poly a, modint c) {
for (auto &v : a.vec) v *= c;
return a;
}
inline Poly operator*=(const Poly & b) { return *this = *this * b; }
inline friend Poly operator-(const Poly &a, const Poly &b) {
vector<modint> c(max(a.size(), b.size()));
for (int i = 0; i < c.size(); i++) c[i] = a[i] - b[i];
return c;
}
inline friend Poly operator+(const Poly &a, const Poly &b) {
vector<modint> c(max(a.size(), b.size()));
for (int i = 0; i < c.size(); i++) c[i] = a[i] + b[i];
return c;
}
inline Poly operator-=(const Poly &b) { return *this = *this - b; }
inline Poly operator+=(const Poly &b) { return *this = *this + b; }
inline Poly operator*=(modint b) { return *this = *this * b; }
inline Poly derivative() const {
if (vec.empty()) return Poly();
vector<modint> z(size() - 1);
for(int i = 1; i < size(); i++) z[i - 1] = vec[i] * i;
return z;
}
inline Poly integrate() const {
vector<modint> z(size() + 1);
for (int i = 1; i <= size(); i++) z[i] = vec[i - 1] / i;
return z;
}
inline Poly inv(int x) const {
Poly z({vec[0].inv()});
int n = 1;
while (n < x) n <<= 1, z = (z * (Poly({2}) - modxk(n) * z)).modxk(n);
return z.modxk(x);
}
inline Poly ln(int x) const {
assert(vec[0] == 1);
return (derivative() * inv(x)).integrate().modxk(x);
}
inline Poly exp(int x) const {
assert(vec[0] == modint(0));
Poly z({1});
int n = 1;
while (n < x)
n <<= 1, z = (z * (Poly({1}) - z.ln(n) + modxk(n))).modxk(n);
return z.modxk(x);
}
inline Poly sqrt(int x) const {
assert(vec[0] == modint(1));
Poly z({1});
int n = 1;
modint inv2 = modint(2).inv();
while (n < x) n <<= 1, z = (z + (modxk(n) * z.inv(n)).modxk(n)) * inv2;
return z.modxk(x);
}
inline void println() {
for (auto c : vec) write(c.value(), ' ');
FastIO::println();
}
};
const int N = 1e5 + 10;
int n, q, B, fa[N];
basic_string<int> vec[N];
Poly c[N], f[N], big[N];
int cc, id[N];
inline Poly mul3(Poly a, Poly b, Poly c) {
if (b.size() > c.size()) swap(b, c);
return (a * b) * c;
}
inline void merge(int x, int y) {
f[x] *= f[y];
if (f[x].size() > B && (id[x] && id[y])) {
++cc;
big[cc] = mul3(f[x], big[id[x]], big[id[y]]);
f[x] = {1};
id[x] = cc;
} else if (f[x].size() > B) ++cc, big[cc] = f[x] * big[id[x]], f[x] = {1}, id[x] = cc;
else if (id[x] && id[y]) ++cc, big[cc] = big[id[x]] * big[id[y]], id[x] = cc;
else id[x] |= id[y];
}
void dfs(int u) {
f[u] = c[u];
if (f[u].size() > B)
++cc, big[cc] = f[u], id[u] = cc, f[u] = {1};
for (int v : vec[u]) if (v != fa[u]) fa[v] = u, dfs(v), merge(u, v);
}
inline modint query(int u, int x) {
if (x < 0) return modint();
modint ans;
if (!id[u]) {
for (int i = 0; i < min(x + 1, int(f[u].size())); i++) ans += f[u][i];
return ans;
}
for (int i = 0; i < min(x + 1, int(f[u].size())); i++) ans += f[u][i] * big[id[u]][min(big[id[u]].size() - 1, x - i)];
return ans;
}
int main() {
read(n, q), B = max(1.0, sqrt(n / log2(n) * 2));
big[0] = {1};
for (int i = 1; i <= n; i++) {
int k;
read(k);
c[i].resize(k + 1);
for (int j = 0, x; j <= k; j++) read(x), c[i][j] = x;
}
for (int i = 1; i < n; i++) {
int u, v;
read(u, v), vec[u] += v, vec[v] += u;
}
dfs(1);
big[++cc] = f[1] * big[id[1]], f[1] = {1}, id[1] = cc;
// cerr << "find id:" << id[1] << endl;
for (int i = 1; i <= cc; i++)
for (int j = 1; j < big[i].size(); j++) big[i][j] += big[i][j - 1];
int last = 0;
while (q--) {
int x, l, r;
read(x, l, r);
x ^= last, l ^= last, r ^= last;
println(last = (query(x, r) - query(x, l - 1)).value());
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
1977 200000 0 883734638 1 497045124 50605999 0 467033353 8 514303373 873913661 21585656 827572829 831599042 669912647 980444584 921677622 90967524 0 111009203 0 980468811 1 965285721 647475291 0 55665482 0 810210109 5 99482052 915734955 536563337 860629716 489661090 127640528 4 452261176 414532348 8...
output:
result:
Subtask #2:
score: 3
Accepted
Test #6:
score: 3
Accepted
time: 42ms
memory: 22192kb
input:
98154 200000 0 948053956 0 149079029 0 871940052 0 888807640 0 284687863 0 760258916 0 916765457 0 121680504 0 210430381 0 162441114 0 640680402 0 269559148 0 706423649 0 619089994 0 776236890 0 44769489 0 863235377 0 283984837 0 251593760 0 863377054 0 40488948 0 100272768 0 628132233 0 18841959 0 ...
output:
0 160622568 939846745 221659137 0 312930382 620657950 975124531 0 241389446 233242086 656904774 0 666641212 127400637 0 0 61866892 388266897 17714856 158666308 181172732 0 231863345 0 0 993493871 0 945624744 0 53582097 0 553931157 940627115 0 864491900 0 0 910285591 0 0 0 0 810021023 0 957355731 870...
result:
ok 200000 numbers
Test #7:
score: 3
Accepted
time: 44ms
memory: 22124kb
input:
98566 200000 0 209181684 0 889317979 0 925862494 0 861680823 0 629292192 0 781545895 0 58892045 0 300501945 0 510137985 0 764792857 0 551445762 0 771899874 0 828696971 0 260462870 0 535761660 0 532161459 0 187099 0 691412616 0 891055462 0 283180276 0 446617517 0 928434806 0 974119517 0 895921491 0 8...
output:
0 541915644 0 0 0 344789573 37160095 0 0 378148422 0 27407348 0 510146116 0 0 593724632 308323897 0 208041958 834526238 308130263 413718362 0 0 452600858 215844992 0 0 138748183 0 597752749 0 0 0 131857104 0 0 583969453 644145934 277456647 0 730806159 210434799 329144450 0 271266199 0 0 532721033 33...
result:
ok 200000 numbers
Subtask #3:
score: 0
Runtime Error
Test #8:
score: 0
Runtime Error
input:
97330 200000 2 356080749 854511831 888131963 0 533633039 0 260190631 0 217335008 2 998111375 903316988 891866314 0 507509609 0 556810297 1 190927168 988903728 1 270553180 387224380 0 360295480 0 775464651 0 755424805 0 71030175 0 690904984 0 702271750 0 360541906 0 903384679 0 769283169 0 6990072 0 ...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #13:
score: 0
Runtime Error
input:
50000 50000 1 610345459 691411093 1 476654936 529767753 1 8856530 640833948 1 961473497 456987897 1 462733802 114971681 1 662244461 415955667 1 717992437 907944693 1 346097988 176526535 1 805826501 182409272 1 33105050 971783530 1 45972429 258997374 1 964103067 796756441 1 958668755 735146502 1 9543...
output:
result:
Subtask #5:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
input:
19854 20000 1 150513542 240180212 0 987796281 0 90054116 1 191708494 438440429 0 192815969 0 867402303 1 531762469 210966860 2 95662022 345368425 199338548 0 269135053 0 816253511 0 66854944 0 319745952 0 202288549 0 492853777 0 410846691 0 824737426 0 821545014 0 72050044 0 534080091 1 542636124 52...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
0%