P11029 题解

ikunTLE · 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;
}