C++ 解法, 执行用时: 136ms, 内存消耗: 408K, 提交时间: 2021-05-22 10:48:39

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int mod=998244353;
ll qmi(ll a,int b)
{
	if(b<0)
	return 0;
	ll res=1;
	while(b)
	{
		if(b&1)	res=res*a%mod;
		b>>=1;
		a=a*a%mod;
	}

	return res;
}
signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin >> n;
		ll res=0;
		ll inv=1;
		for(int i=1;i<=n;i++)
		{
			inv=qmi(i,mod-2)*inv%mod;
			ll res2=0;
			res2=(res2+qmi(2,n-i))%mod;
			res2=(res2+(n-i-1 >=0 ? n-i-1:0)*qmi(2,n-i-2)%mod)%mod;
			res2=res2*inv%mod;
			res=(res+res2)%mod;
		}
	//	cout<<res<<endl;
		res=res*qmi(qmi(2,n-1),mod-2)%mod;
		cout<<res<<endl;
	}
	
	return 0;

}

pypy3(pypy3.6.1) 解法, 执行用时: 545ms, 内存消耗: 31940K, 提交时间: 2021-05-14 21:48:02

M = 998244353
def inv(x): return pow(x,M-2,M)
dp = [0]*500005
sumdp = 0
h = [0]*500005
invfact = [1] * 500005
for n in range(1,500001):
    invfact[n] = invfact[n-1]*inv(n) %M
    if n>1: h[n] = (h[n-1]*2 + invfact[n-1])%M
    dp[n] = (sumdp + h[n] + invfact[n])%M
    sumdp = (sumdp + dp[n]) %M

t = int(input())
while t:
    t -= 1
    n = int(input())
    #print(n,':', dp[n])
    print(dp[n] * inv(pow(2,n-1,M))%M)