QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719725#9608. 皮鞋的多项式peaneval_kala3 55ms22292kbC++2317.5kb2024-11-07 08:27:502024-11-07 08:27:54

Judging History

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

  • [2024-11-07 08:27:54]
  • 评测
  • 测评结果:3
  • 用时:55ms
  • 内存:22292kb
  • [2024-11-07 08:27:50]
  • 提交

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: 49ms
memory: 22064kb

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: 55ms
memory: 22292kb

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%