QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#480163 | #5. 在线 O(1) 逆元 | Williamxzh# | 0 | 0ms | 0kb | C++20 | 1016b | 2024-07-16 09:01:05 | 2024-11-05 22:01:25 |
Judging History
answer
#include <bits/stdc++.h>
#include "inv.h"
#define il inline
#define B __int128
using namespace std;
typedef long long ll;
const int mod=998244353;
il ll qp(ll a,ll b){
ll ans=1ll;
while(b){
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod,b>>=1;
}return ans;
}
const ll N=2e7+5;
int n,fac[N],iv[N],b[31];
void init(int MOD){
n=N-5,fac[0]=1;for(int i=1;i<=n;++i) fac[i]=(1ll*fac[i-1]*i)%mod;
iv[n]=qp(fac[n],mod-2ll);for(int i=n-1;i>=0;--i) iv[i]=(iv[i+1]*(i+1ll))%mod;
for(int i=1;i<=n;++i) iv[i]=(1ll*fac[i-1]*iv[i])%mod;
for(int i=1;i<=29;++i) b[i]=qp(1ll<<i,mod-2ll);
}
il int INV(int x){
if(x<=n) return iv[x];
int y=mod/x;return 1ll*(mod-y)*inv(mod-x*y)%mod;
}
int inv(int x){
if(x&1) return inv(x);
int y=__builtin_ctz(x);
return 1ll*inv(x>>y)*b[y]%mod;
}
/*int main(){
init(mod);
mt19937 rnd(time(0));
for(int i=1;i<=100;++i){
int x=rnd()%(mod-1)+1;
if(inv(x)!=qp(x,mod-2ll)) printf("%d %d %d\n",x,inv(x),qp(x,mod-2ll));
//else puts("*");
}
return 0;
}*/
詳細信息
Pretests
Final Tests
Test #1:
score: 0
Memory Limit Exceeded
Test #2:
score: 0
Memory Limit Exceeded
Test #3:
score: 0
Memory Limit Exceeded
Test #4:
score: 0
Memory Limit Exceeded
Test #5:
score: 0
Memory Limit Exceeded