QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #101598 | #5. 在线 O(1) 逆元 | NOI_AK_ME | 100 ✓ | 2101ms | 19540kb | C++20 | 820b | 2023-04-30 13:57:27 | 2024-11-05 21:48:58 |
Judging History
answer
#pragma once
#pragma GCC optimize("Ofast, unroll-loops")
#include "inv.h"
int djq[3035136], arr[974849];
int inv(int x) {
const int p = (unsigned long long) x * arr[x >> 10] % 998244353;
return (unsigned long long) arr[x >> 10] * (p < 3035136 ? djq[p] : 998244353 - djq[998244353 - p]) % 998244353;
}
int getinv(int x) {
return x == 1 ? 1 : 974849 - (unsigned long long)(974849 / x) * getinv(974849 % x) % 974849;
}
void init(int) {
for(int i = 987;i;--i) {
int inv = getinv(i);
for(int j = 1;j <= 987;++j) {
arr[(unsigned long long) j * inv % 974849] = i;
arr[974849 - (unsigned long long) j * inv % 974849] = 998244353 - i;
}
}
arr[0] = djq[1] = 1;
for(int i = 2;i < 3035136;++i)
djq[i] = 998244353 - (unsigned long long)(998244353 / i) * djq[998244353 % i] % 998244353;
}
Details
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 19ms
memory: 19504kb
Test #2:
score: 20
Accepted
time: 222ms
memory: 19540kb
Test #3:
score: 30
Accepted
time: 1065ms
memory: 19424kb
Test #4:
score: 20
Accepted
time: 1684ms
memory: 19404kb
Test #5:
score: 20
Accepted
time: 2101ms
memory: 19360kb