QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213436 | #6323. Range NEQ | kjhhjki | TL | 36ms | 11760kb | C++14 | 3.1kb | 2023-10-14 14:14:30 | 2023-10-14 14:14:31 |
Judging History
answer
#include<bits/stdc++.h>
#define MAXN 2100006
using namespace std;
typedef unsigned long long _ll;
typedef unsigned int ui;
const ui P = 998244353, G = 3, Gi = 332748118;
inline char nr()
{
static char buf[1<<22],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++;
}
ui read()
{
ui x=0; char ch = nr();
while(!isdigit(ch)) ch=nr();
while(isdigit(ch)) { x=(_ll(x)<<3)+(x<<1)+(ch^48); ch=nr(); }
return x;
}
string strread()
{
string s; char ch = nr();
while(!isdigit(ch)) ch=nr();
while(isdigit(ch)) s.push_back(ch), ch=nr();
return s;
}
ui limit, inv, w[MAXN];
ui qpow(ui x, ui n)
{
ui res = 1;
while(n)
{
if(n&1) res=1ll*res*x%P;
n >>= 1; x=1ll*x*x%P;
}
return res;
}
void init(ui n)
{
limit = 2;
while(limit <= n) limit <<= 1;
for(ui i = 1; i < limit; i <<= 1)
{
ui wn = qpow(G, (P-1)/(i<<1));
w[i] = 1;
for(ui j = i+1; j < (i<<1); ++j)
w[j] = 1ll*w[j-1]*wn%P;
}
inv = qpow(limit, P-2);
}
void NTT(ui a[])
{
for(ui mid = limit>>1; mid >= 1; mid >>= 1)
{
for(ui j = 0; j < limit; j += mid<<1)
{
for(ui k = j, s = mid; k < j+mid; ++k, ++s)
{
ui x = a[k], y = a[k+mid];
a[k] = x+y>P?x+y-P:x+y;
a[k+mid] = 1ll*(x<y?P+x-y:x-y)*w[s]%P;
}
}
}
}
void INTT(ui a[])
{
for(ui mid = 1; mid < limit; mid <<= 1)
{
for(ui j = 0; j < limit; j += mid<<1)
{
for(ui k = j, s = mid; k < j+mid; ++k, ++s)
{
ui x = a[k], y = (1ll * w[s] * a[k+mid])%P;
a[k] = x+y>P?x+y-P:x+y;
a[k+mid] = x<y?P+x-y:x-y;
}
}
}
reverse(a+1, a+limit);
for(ui i = 0; i < limit; ++i)
a[i] = 1ll*a[i]*inv%P;
}
void poly_qpow(ui n, ui k, ui a[], ui res[])
{
init(n<<1); res[0] = 1;
if(k == P)
{
res[0] = a[0];
return;
}
while(k)
{
NTT(a);
if(k&1)
{
NTT(res);
for(ui i = 0; i < limit; ++i)
res[i] = 1ll*res[i]*a[i]%P;
INTT(res);
fill(res+n, res+limit, 0);
}
for(ui i = 0; i < limit; ++i)
a[i] = 1ll*a[i]*a[i]%P;
INTT(a);
fill(a+n, a+limit, 0);
k >>= 1;
}
}
ui n, m, k, inv2, a0, ans, a[MAXN], b[MAXN];
ui fac[MAXN], fac_inv[MAXN];
string s;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
n = read(); m = read(); fac[0] = 1;
for(ui i = 1; i <= n*m; ++i)
fac[i] = 1ll*fac[i-1]*i%P;
fac_inv[n*m] = qpow(fac[n*m], P-2);
for(int i = n*m; i >= 1; --i)
fac_inv[i-1] = 1ll*fac_inv[i]*i%P;
for(int i = 0; i <= m; ++i)
{
a[i] = 1ll*fac[m]*fac_inv[i]%P*fac_inv[m-i]%P*fac_inv[m-i]%P;
if(i&1) a[i] = P-a[i];
}
if(a[0] != 0 && a[0] != 1)
{
inv2 = qpow(a[0], P-2); a0 = a[0];
for(ui i = 0; i <= m; ++i) a[i] = 1ll*a[i]*inv2%P;
}
else inv2 = 1, a0 = 1;
poly_qpow(n*m+1,n,a,b); a0 = qpow(a0,k);
for(ui i = 0; i <= n*m; ++i) ans = (ans + 1ll*b[i]*a0%P*fac[n*m-i]%P)%P;
cout << ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 11672kb
input:
2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11616kb
input:
5 1
output:
44
result:
ok 1 number(s): "44"
Test #3:
score: 0
Accepted
time: 36ms
memory: 11760kb
input:
167 91
output:
284830080
result:
ok 1 number(s): "284830080"
Test #4:
score: 0
Accepted
time: 2ms
memory: 11656kb
input:
2 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 2ms
memory: 11736kb
input:
2 3
output:
36
result:
ok 1 number(s): "36"
Test #6:
score: 0
Accepted
time: 2ms
memory: 11636kb
input:
2 4
output:
576
result:
ok 1 number(s): "576"
Test #7:
score: 0
Accepted
time: 0ms
memory: 11612kb
input:
3 1
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 2ms
memory: 11640kb
input:
3 2
output:
80
result:
ok 1 number(s): "80"
Test #9:
score: 0
Accepted
time: 1ms
memory: 11744kb
input:
3 3
output:
12096
result:
ok 1 number(s): "12096"
Test #10:
score: 0
Accepted
time: 2ms
memory: 11672kb
input:
3 4
output:
4783104
result:
ok 1 number(s): "4783104"
Test #11:
score: 0
Accepted
time: 0ms
memory: 11616kb
input:
4 1
output:
9
result:
ok 1 number(s): "9"
Test #12:
score: 0
Accepted
time: 1ms
memory: 11736kb
input:
4 2
output:
4752
result:
ok 1 number(s): "4752"
Test #13:
score: 0
Accepted
time: 1ms
memory: 11668kb
input:
4 3
output:
17927568
result:
ok 1 number(s): "17927568"
Test #14:
score: 0
Accepted
time: 1ms
memory: 11616kb
input:
4 4
output:
776703752
result:
ok 1 number(s): "776703752"
Test #15:
score: 0
Accepted
time: 0ms
memory: 11704kb
input:
5 2
output:
440192
result:
ok 1 number(s): "440192"
Test #16:
score: 0
Accepted
time: 2ms
memory: 11724kb
input:
5 3
output:
189125068
result:
ok 1 number(s): "189125068"
Test #17:
score: 0
Accepted
time: 0ms
memory: 11624kb
input:
5 4
output:
975434093
result:
ok 1 number(s): "975434093"
Test #18:
score: -100
Time Limit Exceeded
input:
1000 1000