QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #101593 | #5. 在线 O(1) 逆元 | NOI_AK_ME | Judging | / | / | C++20 | 813b | 2023-04-30 13:55:02 | 2024-11-05 21:44:37 |
Judging History
你现在查看的是测评时间为 2024-11-05 21:44:37 的历史记录
- [2024-11-05 21:48:56]
- 管理员手动重测本题所有提交记录
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-04-30 13:55:05]
- 评测
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [2023-04-30 13:55:02]
- 提交
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() {
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;
}