C++(g++ 7.5.0) 解法, 执行用时: 174ms, 内存消耗: 8252K, 提交时间: 2023-04-08 20:57:58

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mod = 998244353;

int n;
ll fac[1000010];

ll qpow(ll x, ll y) {
	ll ans = 1;
	while (y) {
		if (y & 1) {
			ans = ans * x % mod;
		}
		y >>= 1;
		x = x * x % mod;
	}
	return ans % mod;
}

int main() {
	scanf("%d", &n);
	fac[0] = 1;
	for (int i = 1; i <= n; ++ i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	ll ans = 0;
	for (int k = 1; k <= n; ++ k) {
		ans = ans + ((n + 1 - k) * fac[k]) % mod * ((qpow(k + 1, n - k) - qpow(k, n - k)) % mod + mod) % mod;
		ans %= mod;
	}
	ans += n + 1;
	ll res = ans * qpow(fac[n], mod - 2) % mod;
	printf("%lld\n", res);
	return 0;
}

C++ 解法, 执行用时: 173ms, 内存消耗: 456K, 提交时间: 2021-10-18 20:10:37

#include<iostream>
using namespace std;
const int P=998244353;
int n,m,f=1;
inline int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)  res=1ll*res*a%P;
        a=1ll*a*a%P;b>>=1;
    }return res;
}
inline int MOD(int x) {return x-(x>=P)*P;}
int main()
{
    cin>>n;m=n+1;
    for(int k=1;;f=1ll*f*(++k)%P){
        m=MOD(m+1ll*MOD(ksm(k+1,n-k)-ksm(k,n-k)+P)*f%P*(n-k+1)%P);
        if(k==n)  break;
    }cout<<1ll*m*ksm(f,P-2)%P;return 0;
}