三个版本（峰值时间从低到高）

map版

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int P=998244353;
map<int,int>dp;
int calc(int x)
{
	if(x<5)return x;
	if(dp[x])return dp[x];
	return dp[x]=calc(x/2)*calc((x+1)/2)%P;
}
signed main()
{
	int x;scanf("%lld",&x);
	printf("%lld\n",calc(x));
	return 0;
}

记忆化版

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7,P=998244353;
int dp[N+10];
int calc(int x)
{
	if(x<5)return x;
	int s=calc(x/2);
	if(x<=N)
	{
		if(dp[x])return dp[x];
		if(x%2==0)dp[x]=s*s%P;
		else dp[x]=s*calc((x+1)/2)%P;
		return dp[x];
	}
	if(x%2==0)return s*s%P;
	return s*calc((x+1)/2)%P;
}
signed main()
{
	int x;scanf("%lld",&x);
	printf("%lld\n",calc(x));
	return 0;
}

预处理版

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7,P=998244353;
int dp[N+10];
int calc(int x)
{
	if(x<=N)return dp[x];
	int s=calc(x/2);
	if(x%2==0)return s*s%P;
	return s*calc((x+1)/2)%P;
}
signed main()
{
	int x;scanf("%lld",&x);
	for(int i=1;i<=min(N,x);i++)
	{
		if(i<5)dp[i]=i;
		else dp[i]=dp[i/2]*dp[(i+1)/2]%P;
	}
	printf("%lld\n",calc(x));
	return 0;
}