自动搬运

查看原文

来自洛谷，原作者为

	ikunTLE 互关条件见主页（luogu.me/paste/1ij66blw），关注我可以获得我小号 OIerDb 的关注（需私信） || 最后在线时间：2025年8月24日22时50分

搬运于2025-08-24 23:03:37，当前版本为作者最后更新于2024-09-08 18:39:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

思路

考虑使用前缀积与快速幂。

不难发现，第 $3$ 层循环中的 $k^k$ 的值永远不变。可以从第 $3$ 向第 $1$ 层循环用前缀积初始化。对于 $k^k$ 的计算，考虑使用快速幂。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=2e6+10,MOD=998244353;
long long f1[N],f2[N],f3[N];
long long q_pow(long long a,long long b){
	long long ans=1,p=a;
	while(b){
		if(b%2==1)
			ans=ans*p%MOD;
		b/=2;
		p=p*p%MOD;
	}
	return ans;
}
int main(){
	int n=read();
	long long res=1;
	for(int i=1;i<=n;++i)
		f1[i]=q_pow(i,i);
	f2[1]=f1[1];
	for(int i=2;i<=n;++i)
		f2[i]=f2[i-1]*f1[i]%MOD;
	f3[1]=f2[1];
	for(int i=2;i<=n;++i)
		f3[i]=f3[i-1]*f2[i]%MOD;
	for(int i=1;i<=n;++i)
		res=(res*f3[i])%MOD;
	printf("%lld\n",res);
	return 0;
}