YC359D [ 20241029 CQYC NOIP 模拟赛 T4 ] 平方(square)

题意

与 P9994 相同。

模数改为 \(998244353\)。

Sol

有点魔怔了。

注意到我们代码中存在：

if (siz[x] <= bsk) {
    for (auto k : idx[x]) {
        isl[sy[k]] -= val[k];
        val[k] = 1ll * val[k] * val[k] % mod;
        isl[sy[k]] += val[k];
    }
}

这段内层会使用 \(10 ^ 9\) 次。

欸，于是我们就跑了 \(\texttt{10s}\)，怎么绘事捏。

哦，原来 tmd 随机访问很慢啊！

于是我们改成 \(\texttt{pair}\) 直接扔进 \(\texttt{idx}\) 里面。

if (siz[x] <= bsk) {
    for (auto &[k, y] : idx[x]) {
        isl[y] += mod - k;
        k = 1ll * k * k % mod;
        isl[y] += k;
    }
}

直接就跑到 \(\texttt{1s}\) 之内了。

剩下的就是，注意到 \(2 ^ 23 \times 119 = mod - 1\)。

于是我们大胆猜测指数有循环节！！欸一跑，循环节长度只有 \(24\)！！！

预处理出 \(n\) 个底数所有的循环节即可。

复杂度：\(O(n \sqrt n)\)。

Code

#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <tuple>
#include <vector>
#include <cmath>
#define ll long long
#define il inline
#define rg register
#define pii pair <int, int>
using namespace std;
/* #ifdef ONLINE_JUDGE */

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
#define putchar(x) *(u++) = (x)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 24], *u = ubuf;

/* #endif */
int read() {
    int p = 0, flg = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') flg = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        p = p * 10 + c - '0';
        c = getchar();
    }
    return p * flg;
}
void write(int x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
bool _stmer;

#define fi first
#define se second

const int N = 1.2e6 + 5, mod = 998244353;

array <int, N> sx, sy, val;

il void Mod(rg int &x) {
    if (x >= mod) x -= mod;
    if (x < 0) x += mod;
}

int pow_(int x, int k) {
    int ans = 1;
    while (k) {
        if (k & 1) ans = 1ll * ans * x % mod;
        x = 1ll * x * x % mod;
        k >>= 1;
    }
    return ans;
}

array <array <int, 47>, N> req;

il int query(int x, int k) {
    if (x <= 23) return req[k][x];
    return req[k][23 + (x - 23) % 24];
}

array <vector <pii>, N> idx;
array <vector <int>, N> idy;

array <int, N> siz, tag;

array <ll, N> isl;

const int bsk = 5095;

bool _edmer;
int main() {
    cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
    int n = read(), q = read();
    for (int i = 1; i <= n; i++)
        sx[i] = read(), sy[i] = read(), val[i] = read();
    for (int i = 1; i <= n; i++)
        siz[sx[i]]++, idx[sx[i]].push_back(make_pair(val[i], sy[i]));
    for (int i = 1; i <= n; i++)
        if (siz[sx[i]] > bsk) idy[sy[i]].push_back(i);
        else isl[sy[i]] += val[i];
    for (int j = 1; j <= n; j++) {
        req[j][0] = val[j];
        for (int i = 1; i <= 46; i += 2) {
            req[j][i] = 1ll * req[j][i - 1] * req[j][i - 1] % mod;
            req[j][i + 1] = 1ll * req[j][i] * req[j][i] % mod;
        }
    }
    int tot = 0;
    while (q--) {
        int op = read(), x = read();
        if (op == 1) {
            if (siz[x] <= bsk) {
                for (auto &[k, y] : idx[x]) {
                    isl[y] += mod - k;
                    k = 1ll * k * k % mod;
                    isl[y] += k;
                }
            }
            else tag[x]++;
        }
        else {
            ll ans = isl[x];
            for (auto k : idy[x])
                ans += query(tag[sx[k]], k);
            write(ans % mod), putchar(10);
        }
    }
/* #ifdef ONLINE_JUDGE */
    fwrite(ubuf, 1, u - ubuf, stdout);
/* #endif */
    return 0;
}