UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#205197#3673. 20240629_Bnullptr_qwq1001511ms20752kbC++4.0kb2024-06-29 09:33:012024-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