QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#101598#5. 在线 O(1) 逆元NOI_AK_ME100 ✓3860ms19196kbC++20820b2023-04-30 13:57:272023-04-30 14:00:21

Judging History

This is a historical verdict posted at 2023-04-30 14:00:21.

  • [2024-11-05 21:48:58]
  • 管理员手动重测本题所有提交记录
  • Verdict: 100
  • Time: 2101ms
  • Memory: 19540kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-30 14:00:21]
  • Judged
  • Verdict: 100
  • Time: 3860ms
  • Memory: 19196kb
  • [2023-04-30 13:57:27]
  • Submitted

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;
}

详细

Test #1:

score: 30
Accepted
time: 28ms
memory: 19176kb

Test #2:

score: 40
Accepted
time: 410ms
memory: 19196kb

Test #3:

score: 30
Accepted
time: 3860ms
memory: 19168kb