C++11(clang++ 3.9) 解法, 执行用时: 1510ms, 内存消耗: 37064K, 提交时间: 2020-08-29 20:04:00

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+5;
const int mod=998244353;
const int g=3;
const int gi=332748118;//invg
ll kpow(ll a,ll b,int p){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
int phi(int x){
    int ans=x;
    for(int i=2;i*i<=x;i++)
        if(x%i==0){
            while(x%i==0)x/=i;
            ans/=i;ans*=i-1;
        }
    if(x>1)ans=ans/x*(x-1);
    return ans;
}
int up,L,R[maxn<<1];
void ntt_init(int n,int m){
    up=1;L=0;
    while(up<n+m+2)up<<=1,L++;
    for(int i=0;i<up;i++)
        R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
}
int a[maxn<<1],b[maxn<<1],c[maxn<<1];
void ntt(int a[],int type)
{
    for(int i=0;i<up;i++)
        if(i<R[i])swap(a[i],a[R[i]]);
    for(int mid=1;mid<up;mid<<=1){
        ll wn=kpow(type==1?g:gi,(mod-1)/(mid<<1),mod);
        for(int r=mid<<1,j=0;j<up;j+=r){
            ll w=1;
            for(int k=0;k<mid;k++,w=w*wn%mod){
                int x=a[j+k],y=w*a[j+k+mid]%mod;
                a[j+k]=(x+y)%mod;
                a[j+k+mid]=(x-y+mod)%mod;
            }
        }
    }
}
int f[maxn];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1,t=n;i<=n;i++)a[kpow(i,t,k)]++;
    for(int i=1,t=kpow(n,n,k-1)+k-1;i<=n;i++)b[kpow(i,t,k)]++;
    for(int i=1,t=kpow(n,kpow(n,n,phi(k-1))+phi(k-1),k-1)+k-1;i<=n;i++)f[kpow(i,t,k)]++;
    ntt_init(k,k);
    ntt(a,1);ntt(b,1);
    for(int i=0;i<up;i++)c[i]=1ll*a[i]*b[i]%mod;
    ntt(c,-1);
    int inv=kpow(up,mod-2,mod);
    ll ans=0;
    for(int i=0;i<=k+k;i++)ans=(ans+1ll*c[i]*inv%mod*f[i%k]%mod)%mod;
    printf("%lld\n",ans);
}