前言

考场上没想出来，收到来自题目标题的嘲讽

题目大意

求 ∑i=1ni!ik(mod998244353)\sum\limits_{i=1}^n\frac{i!}{i^k}\left(\mod 998244353\right)i=1∑n​iki!​(mod998244353) ，其中 n(1≤2×107),k(1≤k≤2×107)n(1\le 2\times10^7),k(1\le k\le 2\times 10^7)n(1≤2×107),k(1≤k≤2×107) 为输入给出。

解题思路

对于暴力思路，直接爆算即可，时间复杂度为 O((log⁡2k+log⁡2998244353)×n)O\left(\left(\log_2k+\log_2998244353\right)\times n\right)O((log2​k+log2​998244353)×n) 大常数 O(n)O(n)O(n) 但常数太大，过不去。
考虑优化——预处理。我们可以预处理出 1∼n1\sim n1∼n 范围内所有数的 kkk 次方在mod998244353\mod 998244353mod998244353 意义下的逆元，进一步思考，由于 a=b×ca=b\times ca=b×c 则 a−1=b−1×c−1a^{-1}=b^{-1}\times c^{-1}a−1=b−1×c−1，可以使用欧拉筛进行处理。具体地说，就算对于每个质数，可以直接计算其 kkk 次方的逆元：

for(int i=2;i<=n;i++){if(!a[i]){ans[++tot]=i;a[i]=_pow(_pow(i,m),Mod-2);//此处}for(int j=1;j<=tot&&ans[j]*i<=n;j++){a[ans[j]*i]=a[ans[j]]*a[i]%Mod;if(i%ans[j]==0)break;}}

而对于合数，则将其拆成两个数相乘，借此得到其逆元：

for(int i=2;i<=n;i++){if(!a[i]){ans[++tot]=i;a[i]=_pow(_pow(i,m),Mod-2);}for(int j=1;j<=tot&&ans[j]*i<=n;j++){a[ans[j]*i]=a[ans[j]]*a[i]%Mod;//此处if(i%ans[j]==0)break;}}

代码实现

#include
using namespace std;
const long long Mod=998244353;
long long n,m,tot,a[20000010],output,now=1;
int ans[5000010];
long long _pow(long long d,long long z)
{long long ans=1;while(z){if(z&1)ans=ans*d%Mod;d=d*d%Mod;z>>=1;}return ans;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);freopen("math.in","r",stdin);freopen("math.out","w",stdout);cin>>n>>m;a[1]=1;for(int i=2;i<=n;i++){if(!a[i]){ans[++tot]=i;a[i]=_pow(_pow(i,m),Mod-2);}for(int j=1;j<=tot&&ans[j]*i<=n;j++){a[ans[j]*i]=a[ans[j]]*a[i]%Mod;if(i%ans[j]==0)break;}}for(int i=1;i<=n;i++){
//		cout<