Submission #43669944

---

Source Code Expand

#include <atcoder/convolution>
#include <atcoder/modint>

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
using namespace atcoder;

using mint = modint998244353;

const int MAXN = 1e5+100,mod = 998244353;

typedef vector<mint> vec;

ll n,m,K;

mint ans;
//

mint f[MAXN],pw[MAXN],sC[MAXN];

mint iv[MAXN],ivm[MAXN],prod;

mint fac[MAXN],rfac[MAXN];
mint C(ll n,ll m){
	if(n<m || m<0)return 0;
	return fac[n] * rfac[m] * rfac[n-m];
}

mint F1(ll x){
	if(x<0)return 0;
	return sC[x] - x*C(n,x+1);
}
mint F2(ll x){
	if(x<0)return 0;
	return 1 - C(n,x+1);
}


mint F1(ll L,ll R){
	R = min(R,n);
	if(L>R)return 0;
		
	return F1(R) - F1(L-1); 
}
mint F2(ll L,ll R){
	R = min(R,n);
	if(L>R)return 0;

	return F2(R) - F2(L-1);
}

namespace INV{
    vec solve(vec A,int N){
        if(N==1){
            vec ret(1);
            ret[0]=A[0].inv();
            return ret;
        }
        vec F0=solve(A,(N+1)>>1);
        A.resize(N,0);
        A=convolution(A,F0);A.resize(N,0);
        A=convolution(A,F0);A.resize(N,0);
        F0.resize(N,0);
        rep(i,0,N-1)F0[i]=F0[i]*2-A[i];
        return F0;
    }  
};
vec inv(vec p,int N){return INV::solve(p,N+1);}

mint b[MAXN]; //伯努利数

namespace Poly{
	void calc_b(){
		vec x(n+2),B(n+2),F(n+2);
		x[0] = 1;
		rep(i,1,n+2)x[i-1] = rfac[i];

		x = inv(x,n+1);
		rep(i,0,n+1){

			B[i] = x[i];
			F[i] = ((mint)(m+1)).pow(i+1) * rfac[i+1];
		}
		F = convolution(F,B);

		rep(i,0,n){
			mint psum = fac[i] * F[i];

			ans += f[i]*psum;
		}
	}

	void calc(){
		calc_b();
	}
};

int main(){
	cin>>n>>m;

	K = n+5;

	iv[0] = 1;
	rep(i,1,K)iv[i] = iv[i-1] / i;

	if(m > K){
		prod = 1;
		rep(i,1,K)prod = prod * (m-1-i),ivm[i] = iv[i-1] * iv[K-i] / (m-1-i);
	}

	
	pw[0] = 1;rep(i,1,n)pw[i] = pw[i-1] * m;

	fac[0] = 1;rep(i,1,n+5)fac[i] = fac[i-1] * i;
	rep(i,0,n+5)rfac[i] = fac[i].inv();
	
	sC[0] = 1;
	rep(i,1,n)sC[i] = sC[i-1] + C(n,i);
	
	
	//求出多项式f
	vec A(n+1),B(n+1);
	
	rep(j,0,n){
		ll L = max(1LL,n-2*j),R = n;
		mint x = (F1(L+j,R+j) - j*F2(L+j,R+j)) * fac[n-j];

		A[j] = x;		
	}
	rep(i,0,n){
		if(i&1)B[i] = -rfac[i];
		else B[i] = rfac[i]; 
	}
	

	A = convolution(A,B);
	
	rep(i,0,n){
		f[i] = A[i] * pw[n-i] * rfac[n-i];
	}

	//计算
	
	Poly::calc();

	//
	ll S = (m*(m+1)/2)%mod;
	mint ret = m;ret = ret.pow(n-1);

	ret = ret * S * n;

	ans = ret-ans;
	cout<<ans.val()<<endl;
	
    return 0;
}

Submission Info

Judge Result