ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#205197 | #3673. 20240629_B | nullptr_qwq | 100 | 1511ms | 20752kb | C++ | 4.0kb | 2024-06-29 09:33:01 | 2024-06-29 13:04:02 |
answer
// 私は猫です
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define dF(i,a,b) for(int i=(a);i>=(b);i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
using namespace std;
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
const int mod=998244353,maxn=500005;
inline int qpow(int x,ll y){
int rt=1;
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) rt=1ll*rt*x%mod;
return rt;
}
inline void inc(int &x,int y){ x=(x+y>=mod)?(x+y-mod):(x+y); }
inline void dec(int &x,int y){ x=(x>=y)?(x-y):(x+mod-y); }
inline void mul(int &x,int y){ x=1ll*x*y%mod; }
inline int add(int x,int y){ return (x+y>=mod)?(x+y-mod):(x+y); }
inline int sub(int x,int y){ return (x>=y)?(x-y):(x+mod-y); }
inline int prod(int x,int y){ return 1ll*x*y%mod; }
inline void chkmax(int &x,int y){ x=max(x,y); }
inline void chkmin(int &x,int y){ x=min(x,y); }
vector<int>Wn,rev;
void init_NTT(int N=500005){
Wn.resize(N);
F(i,1,__lg(N)){
int wn=qpow(3,(mod-1)/(1<<i)),now=1;
for(int j=0;j<(1<<(i-1));j++) Wn[(1<<(i-1))+j]=now,mul(now,wn);
}
}
vector<int>add(vector<int>a,vector<int>b){
if(a.size()<b.size())swap(a,b);
F(i,0,(int)b.size()-1)inc(a[i],b[i]);
return a;
}
void NTT(vector<int>&a,int N,int op=1){
int n=a.size(),p=1,k=0;
for(;p<n;p<<=1,k++);
rev.resize(n+1);
F(i,1,n-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
F(i,0,n-1) if(i<rev[i]) swap(a[i],a[rev[i]]);
F(i,1,k) for(int j=0;j<(1<<k);j+=(1<<i)){
int tmp=(1<<(i-1));
F(l,j,j+tmp-1){
int x=a[l],y=prod(a[l+tmp],Wn[tmp+l-j]);
a[l]=add(x,y),a[l+tmp]=sub(x,y);
}
}
if(~op) return;
reverse(a.begin()+1,a.end());
a.resize(N);
for(k=1;k<=N;k<<=1);
int inv=qpow(k,mod-2);
F(i,0,N-1) mul(a[i],inv);
}
vector<int>conv(vector<int>a,vector<int>b){
int n=(int)a.size(),m=(int)b.size(),k=1;
for(;k<n+m;k<<=1);
a.resize(k),b.resize(k);
NTT(a,n,1),NTT(b,m,1);
F(i,0,k-1) mul(a[i],b[i]);
NTT(a,n+m-1,-1);
return a;
}
vector<int>getinv(int n,vector<int>a){
if(n==1) {
vector<int>vec;
vec.push_back(qpow(a[0],mod-2));
return vec;
}
vector<int>b=getinv((n+1)>>1,a),c;
F(i,0,n-1) c.push_back(a[i]);
int p=1;
for(;p<(n<<1);p<<=1);
c.resize(p),b.resize(p);
NTT(c,n,1),NTT(b,n,1);
F(i,0,p-1) c[i]=1ll*b[i]*sub(2,1ll*b[i]*c[i]%mod)%mod;
NTT(c,p-1,-1);
c.resize(n);
return c;
}
int n,m,coef[maxn],pre[maxn];
namespace combi{
int fac[maxn],ifac[maxn],inv[maxn],pw[maxn];
void Init(int N){
fac[0]=ifac[0]=inv[0]=pw[0]=1;
F(i,1,N) pw[i]=1ll*pw[i-1]*m%mod;
F(i,1,N) fac[i]=1ll*fac[i-1]*i%mod;
ifac[N]=qpow(fac[N],mod-2);
dF(i,N-1,1) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
F(i,1,N) inv[i]=1ll*ifac[i]*fac[i-1]%mod;
}
inline int C(int n,int m){
if(m>n||n<0||m<0) return 0;
return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
}
using namespace combi;
void solve(){
n=read(),m=read(),Init(maxn-3);
F(i,0,n) pre[i]=C(n,i);
F(i,1,n) inc(pre[i],pre[i-1]);
vector<int>f(n+1),g(n+1);
F(i,0,n){
if(i<=(n>>1)) f[i]=add(pre[i-1],1ll*C(n,i)*(n-(i<<1))%mod);
else f[i]=pre[n-i-1];
mul(f[i],fac[n-i]);
}
F(i,0,n) g[i]=(i&1)?ifac[i]:mod-ifac[i];
g=conv(f,g);
F(i,0,n) coef[i]=1ll*g[i]*pw[n-i]%mod*ifac[n-i]%mod;
f.resize(n+2),g.resize(n+2);
F(i,0,n+1) f[i]=ifac[i+1];
f=getinv(n+2,f);
int tot=1;
F(i,0,n+1) g[i]=1ll*tot*ifac[i]%mod,mul(tot,m+1);
g=conv(f,g);
int ans=1ll*n*(m-1)%mod*pw[n]%mod;
mul(ans,((mod+1)>>1));
F(i,0,n) inc(ans,1ll*coef[i]*sub(g[i+1],f[i+1])%mod*fac[i]%mod);
dec(ans,coef[0]);
printf("%d\n",ans);
}
signed main(){
init_NTT();
int sjy=1;
cmh(sjy) solve();
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 7ms
memory: 10824kb
input:
2 4
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: 5
Accepted
time: 10ms
memory: 10828kb
input:
3 5
output:
200
result:
ok 1 number(s): "200"
Test #3:
score: 5
Accepted
time: 15ms
memory: 10828kb
input:
3 2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 5
Accepted
time: 15ms
memory: 10824kb
input:
4 1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 5
Accepted
time: 12ms
memory: 10828kb
input:
45 69219421
output:
148241603
result:
ok 1 number(s): "148241603"
Test #6:
score: 5
Accepted
time: 8ms
memory: 10824kb
input:
27 165602203
output:
658554778
result:
ok 1 number(s): "658554778"
Test #7:
score: 5
Accepted
time: 8ms
memory: 10828kb
input:
45 475178315
output:
750303667
result:
ok 1 number(s): "750303667"
Test #8:
score: 5
Accepted
time: 8ms
memory: 10828kb
input:
38 575625447
output:
596329899
result:
ok 1 number(s): "596329899"
Test #9:
score: 5
Accepted
time: 15ms
memory: 10824kb
input:
50 547594763
output:
113067713
result:
ok 1 number(s): "113067713"
Test #10:
score: 5
Accepted
time: 13ms
memory: 10828kb
input:
50 939205017
output:
979077924
result:
ok 1 number(s): "979077924"
Test #11:
score: 5
Accepted
time: 7ms
memory: 11100kb
input:
1722 420732765
output:
71025784
result:
ok 1 number(s): "71025784"
Test #12:
score: 5
Accepted
time: 11ms
memory: 11056kb
input:
1079 85508333
output:
664720037
result:
ok 1 number(s): "664720037"
Test #13:
score: 5
Accepted
time: 15ms
memory: 11096kb
input:
1684 633704282
output:
406634186
result:
ok 1 number(s): "406634186"
Test #14:
score: 5
Accepted
time: 14ms
memory: 11096kb
input:
1674 72493705
output:
298808914
result:
ok 1 number(s): "298808914"
Test #15:
score: 5
Accepted
time: 132ms
memory: 15964kb
input:
55406 83254279
output:
327402485
result:
ok 1 number(s): "327402485"
Test #16:
score: 5
Accepted
time: 260ms
memory: 20752kb
input:
98826 891636151
output:
541392819
result:
ok 1 number(s): "541392819"
Test #17:
score: 5
Accepted
time: 252ms
memory: 18040kb
input:
68127 378267026
output:
883696916
result:
ok 1 number(s): "883696916"
Test #18:
score: 5
Accepted
time: 247ms
memory: 18092kb
input:
70675 565507021
output:
224720528
result:
ok 1 number(s): "224720528"
Test #19:
score: 5
Accepted
time: 304ms
memory: 19744kb
input:
87863 589129752
output:
768577490
result:
ok 1 number(s): "768577490"
Test #20:
score: 5
Accepted
time: 158ms
memory: 16256kb
input:
56948 649115566
output:
40413672
result:
ok 1 number(s): "40413672"
Extra Test:
score: 0
Extra Test Passed