求助卡常qwq
- 板块P9060 [Ynoi2002] Goedel Machine
- 楼主lOpzIth
- 当前回复3
- 已保存回复3
- 发布时间2023/8/6 02:57
- 上次更新2023/11/3 05:38:59
查看原帖
被骇客银狼阻止的越权访问保存失败
求助卡常qwq
#include<bits/stdc++.h>
//#define int long long
#define Arr std::vector
#define eb emplace_back
#define pb push_back
#define N 100005
#define SQ 318
#define P 998244353
#define MOD 998244352
int n, m, B, cur, tgh, a[N], qwq[N], ans[N], opt[N], OPT[N], Vis[N];
int vis[N], minp[N], pri[N], id[N], maxx[8] = {0, 16, 10, 7, 5, 4, 4, 4}, bit[N << 1], lop[N];
std::array<int, 3> Q[N];
Arr<int> Mul[N], Inv[N];
int cnt[N][66][3], CNT[N][15][17];
class FastIostream {
const int maxBF = 1 << 20;
char *inbuf, *inst, *ined, *oubuf, *oust, *oued;
void _flush() { fwrite(oubuf, 1, oued - oust, stdout); }
char _getchar() {
if (inst == ined) inst = inbuf, ined = inbuf + fread(inbuf, 1, maxBF, stdin);
return inst == ined ? EOF : *inst++;
} void _putchar(const char &c) {
if (oued == oust + maxBF) _flush(), oued = oubuf;
*oued++ = c;
}
public:
FastIostream() {
inst = ined = inbuf = new char[maxBF];
oust = oued = oubuf = new char[maxBF];
} ~FastIostream() {_flush();}
template <typename Int> FastIostream &operator>>(Int &n) {
static char c;
bool flag = false;
while ((c = _getchar()) < '0' || c > '9') if (c == '-') flag = true;
for (n = c - '0'; (c = _getchar()) >= '0' && c <= '9'; n = n * 10 + (c - 48));
if (flag) n = ~n + 1;
return *this;
} template <typename Int> FastIostream &operator<<(Int n) {
if (n < 0) _putchar('-'), n = ~n + 1;
static char S[40];
int t = 0;
do {S[t++] = '0' + n % 10, n /= 10;} while (n);
for (int i = 0; i < t; ++i) _putchar(S[t - i - 1]);
return *this;
} FastIostream &operator<<(const char *s) {
for (int i = 0; s[i]; ++i) _putchar(s[i]);
return *this;
}
} io;
inline int Pow(int x, int y)
{
int res = 1ll;
for (; y; y >>= 1)
{
if (y & 1) res = (1ll * res * x) % P;
x = (1ll * x * x) % P;
}
return res;
}
void Sieve()
{
minp[1] = 1;
for (int i = 2; i < N; i++)
{
if (!vis[i]) pri[++cur] = i, id[i] = cur, minp[i] = i;
for (int j = 1; j <= cur && pri[j] * i < N; j++)
{
vis[pri[j] * i] = 1;
minp[pri[j] * i] = pri[j];
if (!(i % pri[j])) break;
}
}
bit[0] = 1ll;
for (int i = 1; i < N; i++) bit[i] = (bit[i - 1] << 1) % MOD;
}
signed main()
{
//freopen("ddickky4.in", "r", stdin);
//freopen("ddickky.out", "w", stdout);
io >> n >> m; B = std::sqrt(n);
Sieve(); //printf("%lld\n", id[317]);
for (int i = 1; i <= n; i++) io >> a[i];
for (int i = 1; i <= m; i++)
{
register int l, r; io >> l >> r;
Q[i] = {l, r, i};
}
std::sort(Q + 1, Q + m + 1, [](std::array<int, 3> x, std::array<int, 3> y)
{
int t1 = x[0] / B, t2 = y[0] / B;
if (t1 == t2 && (t1 & 1)) return x[1] > y[1];
else if (t1 == t2 && !(t1 & 1)) return x[1] < y[1];
return t1 < t2;
});
//std::cout << "time = " << (double)clock() / CLOCKS_PER_SEC << "s" << '\n';
for (int i = 1; i <= n; i++)
{
int ty = a[i];
CNT[i][1][1] = CNT[i - 1][1][1];
CNT[i][1][2] = CNT[i - 1][1][2];
CNT[i][1][3] = CNT[i - 1][1][3];
CNT[i][1][4] = CNT[i - 1][1][4];
CNT[i][1][5] = CNT[i - 1][1][5];
CNT[i][1][6] = CNT[i - 1][1][6];
CNT[i][1][7] = CNT[i - 1][1][7];
CNT[i][1][8] = CNT[i - 1][1][8];
CNT[i][1][9] = CNT[i - 1][1][9];
CNT[i][1][10] = CNT[i - 1][1][10];
CNT[i][1][11] = CNT[i - 1][1][11];
CNT[i][1][12] = CNT[i - 1][1][12];
CNT[i][1][13] = CNT[i - 1][1][13];
CNT[i][1][14] = CNT[i - 1][1][14];
CNT[i][1][15] = CNT[i - 1][1][15];
CNT[i][1][16] = CNT[i - 1][1][16];
CNT[i][2][1] = CNT[i - 1][2][1];
CNT[i][2][2] = CNT[i - 1][2][2];
CNT[i][2][3] = CNT[i - 1][2][3];
CNT[i][2][4] = CNT[i - 1][2][4];
CNT[i][2][5] = CNT[i - 1][2][5];
CNT[i][2][6] = CNT[i - 1][2][6];
CNT[i][2][7] = CNT[i - 1][2][7];
CNT[i][2][8] = CNT[i - 1][2][8];
CNT[i][2][9] = CNT[i - 1][2][9];
CNT[i][2][10] = CNT[i - 1][2][10];
CNT[i][3][1] = CNT[i - 1][3][1];
CNT[i][3][2] = CNT[i - 1][3][2];
CNT[i][3][3] = CNT[i - 1][3][3];
CNT[i][3][4] = CNT[i - 1][3][4];
CNT[i][3][5] = CNT[i - 1][3][5];
CNT[i][3][6] = CNT[i - 1][3][6];
CNT[i][3][7] = CNT[i - 1][3][7];
CNT[i][4][1] = CNT[i - 1][4][1];
CNT[i][4][2] = CNT[i - 1][4][2];
CNT[i][4][3] = CNT[i - 1][4][3];
CNT[i][4][4] = CNT[i - 1][4][4];
CNT[i][4][5] = CNT[i - 1][4][5];
CNT[i][5][1] = CNT[i - 1][5][1];
CNT[i][5][2] = CNT[i - 1][5][2];
CNT[i][5][3] = CNT[i - 1][5][3];
CNT[i][5][4] = CNT[i - 1][5][4];
CNT[i][6][1] = CNT[i - 1][6][1];
CNT[i][6][2] = CNT[i - 1][6][2];
CNT[i][6][3] = CNT[i - 1][6][3];
CNT[i][6][4] = CNT[i - 1][6][4];
CNT[i][7][1] = CNT[i - 1][7][1];
CNT[i][7][2] = CNT[i - 1][7][2];
CNT[i][7][3] = CNT[i - 1][7][3];
CNT[i][7][4] = CNT[i - 1][7][4];
for (int j = 8; j <= 14; j++) CNT[i][j][1] = CNT[i - 1][j][1], CNT[i][j][2] = CNT[i - 1][j][2], CNT[i][j][3] = CNT[i - 1][j][3];
for (int j = 15; j < 67; j++) cnt[i][j][1] = cnt[i - 1][j][1], cnt[i][j][2] = cnt[i - 1][j][2];
while (ty != 1)
{
register int tt = minp[ty], ret = 0, iu = id[tt];
while (minp[ty] == tt) ty /= minp[ty], ret++;
if (tt < SQ)
{
if (tt >= 47)
cnt[i][iu][ret]++;
else
CNT[i][iu][ret]++;
}
else qwq[i] = iu, opt[iu]++, lop[++tgh] = iu;
}
}
//std::cout << "time = " << (double)clock() / CLOCKS_PER_SEC << "s" << '\n';
//std::sort(lop.begin(), lop.end());
//lop.erase(std::unique(lop.begin(), lop.end()), lop.end());
for (int i = 1; i <= tgh; i++)
{
int tt = lop[i];
if (Vis[tt]) continue;
Vis[tt] = 1;
Mul[tt].eb(1); Inv[tt].eb(1);
for (int i = 1; i <= opt[tt]; i++)
{
int tmp = Pow(pri[tt], bit[i] - 1);
Mul[tt].eb(tmp);
Inv[tt].eb(Pow(tmp, P - 2));
}
}
int l = 1, r = 0, aans = 1;
//std::cout << "time = " << (double)clock() / CLOCKS_PER_SEC << "s" << '\n';
auto add = [&](int x)
{
if (!qwq[x]) return ;
int ID = qwq[x];
aans = (1ll * aans * Mul[ID][OPT[ID] + 1] % P * Inv[ID][OPT[ID]]) % P;
OPT[ID]++;
};
auto del = [&](int x)
{
if (!qwq[x]) return ;
int ID = qwq[x];
OPT[ID]--;
aans = (1ll * aans * Mul[ID][OPT[ID]] % P * Inv[ID][OPT[ID] + 1]) % P;
};
for (int i = 1; i <= m; i++)
{
int L = Q[i][0], R = Q[i][1], pos = Q[i][2];
while (l > L) l--, add(l);
while (r < R) r++, add(r);
while (l < L) del(l), l++;
while (r > R) del(r), r--;
ans[pos] = aans;
}
for (int i = 1; i <= m; i++)
{
int L = Q[i][0], R = Q[i][1], pos = Q[i][2];
for (int j = 1; j <= 7; j++)
{
register int tu = 0, up = 0;
for (int k = maxx[j]; k >= 1; k--)
{
int num = CNT[R][j][k] - CNT[L - 1][j][k];
if (!num) continue;
up = (up + 1ll * ((bit[tu + num] - bit[tu]) < 0 ? (bit[tu + num] - bit[tu]) + MOD : (bit[tu + num] - bit[tu])) * k) % MOD;
tu += num;
}
if (!up) continue;
ans[pos] = (1ll * ans[pos] * Pow(pri[j], up)) % P;
}
for (int j = 8; j <= 14; j++)
{
int tu = 0, up = 0, num = CNT[R][j][3] - CNT[L - 1][j][3];
if (num) up = (up + 1ll * ((bit[tu + num] - bit[tu]) < 0 ? (bit[tu + num] - bit[tu]) + MOD : (bit[tu + num] - bit[tu])) * 3ll) % MOD;
tu = num;
num = CNT[R][j][2] - CNT[L - 1][j][2];
if (num) up = (up + 1ll * ((bit[tu + num] - bit[tu]) < 0 ? (bit[tu + num] - bit[tu]) + MOD : (bit[tu + num] - bit[tu])) * 2ll) % MOD;
tu += num;
num = CNT[R][j][1] - CNT[L - 1][j][1];
if (num) up = (up + 1ll * ((bit[tu + num] - bit[tu]) < 0 ? (bit[tu + num] - bit[tu]) + MOD : (bit[tu + num] - bit[tu]))) % MOD;
if (!up) continue;
ans[pos] = (1ll * ans[pos] * Pow(pri[j], up)) % P;
}
for (int j = 15; j <= 66; j++)
{
int tu = 0, up = 0, num = cnt[R][j][2] - cnt[L - 1][j][2];
if (num) up = (up + 1ll * ((bit[tu + num] - bit[tu]) < 0 ? (bit[tu + num] - bit[tu]) + MOD : (bit[tu + num] - bit[tu])) * 2ll) % MOD;
tu = num;
num = cnt[R][j][1] - cnt[L - 1][j][1];
if (num) up = (up + 1ll * ((bit[tu + num] - bit[tu]) < 0 ? (bit[tu + num] - bit[tu]) + MOD : (bit[tu + num] - bit[tu]))) % MOD;
if (!up) continue;
ans[pos] = (1ll * ans[pos] * Pow(pri[j], up)) % P;
}
}
for (int i = 1; i <= m; i++) io << ans[i] << "\n";
//std::cout << "time = " << (double)clock() / CLOCKS_PER_SEC << "s" << '\n';
return 0;
}
加载中...