QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#578375 | #6323. Range NEQ | AKALemon# | RE | 12ms | 24912kb | C++23 | 4.2kb | 2024-09-20 18:44:04 | 2024-09-20 18:44:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using db = double;
constexpr int N = 1e6 + 50, LOGN = 30;
constexpr i64 P = 998244353;
typedef long long ll;
ll pos[N];
const ll mod = 998244353, root = 3;
inline ll fastpow(ll a, ll b) {
ll ans = 1;
for (;b;a=a*a%mod,b>>=1) if(b&1)ans=ans*a%mod;
return ans;
}
inline void exgcd(ll a,ll b,ll &g,ll &x,ll &y) {
if (!b) g=a,x=1,y=0;
else exgcd(b,a%b,g,y,x),y-=x*(a/b);
}
inline ll inv(ll a) {
ll g,x,y;
exgcd(a,mod,g,x,y);
return (x%mod+mod)%mod;
}
void init(const int &n) {
for (int i = 0,j=0; i < n; ++i) {
pos[i]=j;for (int l = n >> 1; (j ^= l) < l; l >>= 1);
}
}
void transform(ll *a, const int &n, bool inverse) {
for (int i=0; i<n;++i) if(i>pos[i]) swap(a[i],a[pos[i]]);
for (int l=2; l<=n;l<<=1) {
int m=l/2;ll omega=fastpow(inverse?inv(root):root,(mod-1)/l);
for (ll *p=a;p!=a+n;p+=l) {
ll x=1;
for (int i=0;i<m;++i,x=x*omega%mod) {
ll t=x*p[m+i]%mod;
p[m+i]=(p[i]-t+mod)%mod;(p[i]+=t)%=mod;
}
}
}
}
void dft(ll *a, const int &n) {
transform(a,n,0);
}
void idft(ll *a, const int &n) {
const ll INV=inv(n);
transform(a,n,1);
for (int i=0;i<n;i++) a[i]=a[i]*INV % mod;
}
const int maxn=4e6+6;
ll a[maxn],b[maxn],c[maxn],pic[maxn],pec[maxn],plc[maxn],ppc[maxn];
int INV[maxn];
void poly_inv(int n,ll *a,ll *b) {
if(n==1) {b[0]=inv(a[0]);return;}
poly_inv((n+1)/2,a,b);
int cnt=1;while(cnt<=n*2) cnt<<=1;init(cnt);
copy(a,a+n,pic);fill(pic+n,pic+cnt,0);fill(b+n,b+cnt,0);dft(pic,cnt);dft(b,cnt);
for(int i=0;i<cnt;i++) (b[i]*=(2ll-pic[i]*b[i])%mod)%=mod;
for(int i=0;i<cnt;i++) b[i]=(b[i]+mod)%mod;
idft(b,cnt);fill(b+n,b+cnt,0);
}
void poly_ln(int n,ll *a,ll *b) { //G'=F'/F
poly_inv(n,a,b);
int cnt=1;while(cnt<=n*2-3) cnt<<=1;init(cnt);
for(int i=0;i<n-1;i++) plc[i]=a[i+1]*(i+1)%mod;
fill(plc+n-1,plc+cnt,0);fill(b+n,b+cnt,0);dft(plc,cnt);dft(b,cnt);
for(int i=0;i<cnt;i++) b[i]=plc[i]*b[i]%mod;
idft(b,cnt);for(int i=n-1;i>=1;i--) b[i]=b[i-1]*INV[i]%mod;b[0]=0;
fill(b+n,b+cnt,0);
}
void poly_exp(int n,ll *a,ll *b) {
if(n==1) {b[0]=1;return;}
poly_exp((n+1)/2,a,b);poly_ln(n,b,pec);
int cnt=1;while(cnt<=n*2-2) cnt<<=1;init(cnt);
for(int i=0;i<n;i++) pec[i]=(-pec[i]+a[i])%mod;pec[0]+=1;
dft(pec,cnt);dft(b,cnt);
for(int i=0;i<cnt;i++) b[i]=(b[i]*pec[i])%mod;
idft(b,cnt);fill(b+n,b+cnt,0);
}
void poly_pow(int n,ll *a,ll *b,ll k) {
poly_ln(n,a,ppc);
for(int i=0;i<n;i++) ppc[i]*=k;
poly_exp(n,ppc,b);
}
i64 fac[N], invfac[N];
i64 C(int n, int m) {
if (n < m) return 0;
if (m < 0) return 0;
return fac[n] * invfac[m] % P * invfac[n - m] % P;
}
void init() {
fac[0] = 1;
for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % P;
invfac[N - 1] = fastpow(fac[N - 1], P - 2);
for (int i = N - 1; i > 0; i--) invfac[i - 1] = invfac[i] * i % P;
}
void solve(){
int n, m; cin >> n >> m;
init();
int limit = 1;
while (limit < n * m + 1) limit *= 2;
init(limit);
for (int i = 0; i <= m; i++) {
a[i] = C(m, i) * C(m, i) % P * fac[i] % P;
}
dft(a, limit);
for (int i = 0; i <= limit; i++) {
a[i] = fastpow(a[i], n);
}
idft(a, limit);
// poly_pow(limit, a, b, n);
// for (int i = 0; i <= n * m; i++) cout << a[i] << ' ';
// auto g = Poly(f).pow(n,)
// int sz = 1;
// while (n * m + 1 > sz) sz *= 2;
// f.resize(sz);
// dft(f);
// for (int i = 0; i <= n * m + 1; i++) f[i] = power(f[i], n);
// idft(f);
// for (int i = 0; i <= n * m + 1; i++) cout << f[i] << ' ';
i64 ans = 0;
for (int i = 0; i <= n * m; i++) {
i64 sign = (i % 2 ? -1 : 1);
ans += sign * fac[n * m - i] % P * a[i] % P;
ans = (ans + P) % P;
}
cout << ans << "\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cout << setprecision(15) << fixed;
int t = 1;
//cin >> t;
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 24144kb
input:
2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 6ms
memory: 24252kb
input:
5 1
output:
44
result:
ok 1 number(s): "44"
Test #3:
score: 0
Accepted
time: 9ms
memory: 23496kb
input:
167 91
output:
284830080
result:
ok 1 number(s): "284830080"
Test #4:
score: 0
Accepted
time: 11ms
memory: 24144kb
input:
2 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 9ms
memory: 24912kb
input:
2 3
output:
36
result:
ok 1 number(s): "36"
Test #6:
score: 0
Accepted
time: 8ms
memory: 23720kb
input:
2 4
output:
576
result:
ok 1 number(s): "576"
Test #7:
score: 0
Accepted
time: 11ms
memory: 23996kb
input:
3 1
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 8ms
memory: 24340kb
input:
3 2
output:
80
result:
ok 1 number(s): "80"
Test #9:
score: 0
Accepted
time: 12ms
memory: 23820kb
input:
3 3
output:
12096
result:
ok 1 number(s): "12096"
Test #10:
score: 0
Accepted
time: 12ms
memory: 24328kb
input:
3 4
output:
4783104
result:
ok 1 number(s): "4783104"
Test #11:
score: 0
Accepted
time: 11ms
memory: 23800kb
input:
4 1
output:
9
result:
ok 1 number(s): "9"
Test #12:
score: 0
Accepted
time: 8ms
memory: 23556kb
input:
4 2
output:
4752
result:
ok 1 number(s): "4752"
Test #13:
score: 0
Accepted
time: 6ms
memory: 24740kb
input:
4 3
output:
17927568
result:
ok 1 number(s): "17927568"
Test #14:
score: 0
Accepted
time: 8ms
memory: 23644kb
input:
4 4
output:
776703752
result:
ok 1 number(s): "776703752"
Test #15:
score: 0
Accepted
time: 12ms
memory: 23864kb
input:
5 2
output:
440192
result:
ok 1 number(s): "440192"
Test #16:
score: 0
Accepted
time: 3ms
memory: 23532kb
input:
5 3
output:
189125068
result:
ok 1 number(s): "189125068"
Test #17:
score: 0
Accepted
time: 8ms
memory: 24716kb
input:
5 4
output:
975434093
result:
ok 1 number(s): "975434093"
Test #18:
score: -100
Runtime Error
input:
1000 1000