QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#143692 | #5. 在线 O(1) 逆元 | ucup-team361 | 100 ✓ | 3767ms | 19416kb | C++17 | 1.2kb | 2023-08-21 14:31:48 | 2024-11-05 21:51:30 |
Judging History
answer
#include<bits/stdc++.h>
#include"inv.h"
using std::cin;
using std::cout;
const int mod = 998244353;
const int mod2 = 974849;
const int w = sqrt(mod2);
const int limit = 3 * (w + 1) * 1024;
int djq[limit], arr[mod2];
using u64 = unsigned long long;
int inv(int x) {
const int p = (u64) x * arr[x >> 10] % mod;
/*
if(p >= limit && p <= mod - limit) {
std::cerr << "debug : " << x << '\n';
}
*/
return (u64) arr[x >> 10] * (p < limit ? djq[p] : mod - djq[mod - p]) % mod;
}
void init(int) {
for(int i = w;i >= 1;--i) {
std::function<int(int)> getinv = [&](int x) {
return x == 1 ? 1 : mod2 - u64(mod2 / x) * getinv(mod2 % x) % mod2;
};
int inv = getinv(i);
for(int j = 1;j <= w;++j) {
arr[(u64) j * inv % mod2] = i;
arr[mod2 - (u64) j * inv % mod2] = mod - i;
}
}
arr[0] = 1;
// 0 <= x * arr[x] - k * mod2 < w, and arr[x] < w, k < w
// 998244353 = mod2 * 1024 - 1023
// 0 <= 1024x * arr[x] - k * 998244353 < w * 1024 + 1023 * k
// 0 <= (1024x + y) * arr[x] - k * 998244353 < w * 1024 + 1023 * k + 1024 * w
djq[1] = 1;
// 等下再优化这个
for(int i = 2;i < limit;++i) {
djq[i] = mod - u64(mod / i) * djq[mod % i] % mod;
}
}
Details
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 23ms
memory: 19416kb
Test #2:
score: 20
Accepted
time: 441ms
memory: 19400kb
Test #3:
score: 30
Accepted
time: 2464ms
memory: 19320kb
Test #4:
score: 20
Accepted
time: 3767ms
memory: 19320kb
Test #5:
score: 20
Accepted
time: 3622ms
memory: 19336kb