QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#299291 | #5. 在线 O(1) 逆元 | xhgua | 100 ✓ | 2824ms | 24108kb | C++14 | 1.0kb | 2024-01-06 18:34:29 | 2024-01-06 18:34:29 |
Judging History
answer
#include "inv.h"
#include <array>
#include <vector>
#include <iostream>
using i64 = long long;
constexpr int P = 998244353;
namespace Inversion {
static constexpr int B = (1 << 10), T = (1 << 20);
std::array<int, T + 1> f, p;
std::array<int, T * 3 + 3> buf;
int *I = buf.begin() + T;
void init() {
for (int i = 1; i <= B; i++) {
int s = 0, d = (i << 10);
for (int j = 1; j <= T; j++) {
if ((s += d) >= P) s -= P;
if (s <= T) {
if (!f[j]) f[j] = i, p[j] = s;
}
else if (s >= P - T) {
if (!f[j]) f[j] = i, p[j] = s - P;
}
else {
int t = (P - T - s - 1) / d;
s += t * d, j += t;
}
}
}
I[1] = f[0] = 1;
for (int i = 2; i <= (T << 1); i++)
I[i] = 1ll * (P - P / i) * I[P % i] % P;
for (int i = -1; i >= -T; i--)
I[i] = P - I[-i];
}
int inv(int x) {
return 1ll * I[p[x >> 10] + (x & 1023) * f[x >> 10]] * f[x >> 10] % P;
}
};
void init(int p) {
Inversion::init();
}
int inv(int x) {
return Inversion::inv(x);
}
詳細信息
Test #1:
score: 30
Accepted
time: 26ms
memory: 24108kb
Test #2:
score: 40
Accepted
time: 283ms
memory: 24044kb
Test #3:
score: 30
Accepted
time: 2824ms
memory: 24040kb