前言
题目链接（突然发现题目名 Shojo,Step,Start 都是 S 耶）
本题是一个题目化简过后的结果，这个化简的过程非常神仙（导致出题人看不懂），于是缩减为了计算一个和式。正解为一个（对咱来说）意向不到的思路——线性筛。我们先从部分分一点点讲起
Subtask1
我会 C++ 的 int operator*(int,int)！暴力通过本 Subtask，复杂度 $O(n^2)$
Subtask2
我会快速幂！使用快速幂通过本 Subtask，复杂度 $O(n \log n)$。顺带一提 $10^6$ 的数据一般用于卡掉 $O(n \log n ^ 2)$ 并且放过 $O(n \log n)$，本题快速幂常数极小（因为幂次并没有卡满），甚至可以卡过 $10^7$ 左右的数据。
Subtask3
首先看到数据范围可以观察出正解复杂度为线性。虽然（对愚蠢的出题人来说）正解并不容易直接想到，但是根据经验显然可以得知既然无法直接计算，我们就需要进行一定程度的预处理来加速计算。怎么预处理？根号分治，素数预处理......泉部试一遍，我们大概可以拼凑出正解的轮廓。
首先，对于素数我们使用快速幂暴力计算答案（这一部分记为 $Part1$），由素数数量可得复杂度为 $O(\frac {n} {\ln n} \times \log n) = O(n)$。
然后对于非素数，我们将其拆解为 $x = pq$，其中 $p$ 为它的最小质因数。根据线性筛的过程，我们在计算完 $q$ 的答案的时候，枚举质因数 $p$ 直到 $p$ 为 $q$ 的因子，这样我们根据 $p,q$ 的答案就可以推出所有非素数 $x$ 的答案，于是便求出了所有答案。这里有一个性质，最小质因数 $p$ 一定小于 $\sqrt x$。
具体来说怎么求呢？在枚举到 $p,q$ 时我们已经计算完了他们的答案，于是有 $x^x = (p \times q) ^ {p \times q} = (p^p)^q \times (q^q)^p = (ans_p) ^ q \times (ans_q) ^ p$。我们称前者为 $Part2$，后者为 $Part 3$。
计算 $Part2$：回想起 $p \le \sqrt x$ 的性质，发现和根号十分相关。然后又想到我们要求每个数的计算是线性的。一个同时和线性，根号，幂次相关的算法，答案呼之欲出——光速幂（没学过的同学可以了解下，其实非常简单，就是根号预处理）。
因为只有小于 $\sqrt x$ 个可能的底数，我们对小于 $\sqrt n$ 的素数进行 $ans_p$ 的光速幂的预处理，每个数 $O(\sqrt n)$ 预处理，$O(1)$ 查询，于是在 $O(\sqrt n \times \sqrt n)$ 预处理，$O(n)$ 复杂度内计算出了 $Part2$。
计算 $Part3$：假设素数为 $pr_1,pr_2,pr_3 \dots $，发现因为我们是在外层枚举 $q$（这部分抽象看不好理解，先去把线性筛的板子写出来就明白了，也可以参考下文代码），内层枚举 $p$，实际上 $Part3$ 是可以被累乘起来的。即我们先计算 $(ans_q) ^ {pr_1} = f_1$，然后计算 $(f_1) ^ {pr_2 - pr_1} = f_2 \dots$ 于是最终 $Part3$ 也可以被计算出来。
然而就算是累乘，暴力乘是单次 $O(n)$ 的。此处需要用到一个非常 NT（nice try）的结论（或者你可以通过敏锐的观察力得出），$pr_x - pr_{x-1}$ 是一个叫做 “prime gap”的东西，它的大小为 $\ln x$ 级别（？这个东西真的冷门，咱在百度上都没查到这个结论）。因为要求 $p \times q \le n$，实际范围是 $\ln \frac {n} {q}$。
于是得出总的复杂度为 $\sum \limits _{i = 1} ^{n} \ln \frac {n} {i}$，为 $O(n)$ 级别的（btw，实践发现它的值大约为 $\frac n 2$），我们便在 $O(n)$ 复杂度内求出了 $Part3$。
你也许会说“这也太难想到了吧”，但是如果你足够敏锐，可以在没有这个结论的情况下发现 $pr_i - pr_{i-1}$ 的值的确很小，可以通过记忆化的方式来求出它（事实上这也是推荐的实现方式，因为 “prime gap” 的上界确实不好卡，而且每次跑满常数也很大）。
总结：我们通过暴力快速幂求出 $Part1$，通过对根号值域内进行光速幂预处理求出 $Part2$，通过对每个数进行 $(ans_i)^x$ 的记忆化求出 $Part3$。总复杂度是线性的。
(并不存在的)Subtask4
由于出题人在造数据的时候忘记放进去了（而且懒得改），没有放置这个 $k = 0$ 的数据点。想想该怎么做？
首先各位猜猜为什么不直接求和式或者异或，而是要加上一个数？
因为参数（输入）只有一个数，这给了打表很大的空间。而即使是暴力（快速幂）也能在较快的时间内算出 $2 \times 10^7$ 的答案，于是我们可以分块打表。并且这个块可以非常大——差不多分块打表 $4 \sim 5$ 个答案就可以过掉本题。
顺带一提，对于原题来说（没有这个奇怪的限制），分块打表效率是最高的——只需要 $10$ 行不到的代码便可以完成。考虑到这其实只是原题的最后一小部分，如果完泉使用正解的话代码复杂度和调试复杂度将会极高。所以说关键时候偷下懒还是很有必要的。
代码
#include<bits/stdc++.h>
#define Akano 1
#define pure__Elysia 0
#define loves ^
using namespace std;
using ll = long long;
constexpr int MOD = 998244353;
constexpr int MAXN = 10181108 * 2;
constexpr int MAXPR = 2e6 + 1018 + 1108;
constexpr int MAXSQT = sqrt(MAXN) + 10 + 18;
inline ll KSM(ll a,ll b){
ll ret = 1;
while(b){
if(b & 1)ret = (ret * a) % MOD;
a = (a * a) % MOD;
b >>= 1;
}
return ret;
}
ll prime[MAXPR],prpow1[MAXSQT][MAXSQT],prpow2[MAXSQT][MAXSQT],prCnt;
bool notp[MAXN];
ll ans[MAXN],p[MAXN],deltaval;
inline ll GetPow(int pri,int x,int sqt){
return (prpow1[pri][x % sqt] * prpow2[pri][x / sqt]) % MOD;
}
inline ll GetPrime(int up){
ll ret = 0;
ans[1] = p[0] = 1;
ret ^= (ans[1] + deltaval) % MOD;
const ll upSQt = sqrt(up);
for(int i = 2;i <= up;i++){
if(notp[i] == false){
prime[++prCnt] = i;
ans[i] = KSM(i,i);
if(i <= upSQt + 2){
prpow1[prCnt][0] = prpow2[prCnt][0] = 1;
for(int j = 1;j <= upSQt;j++){
prpow1[prCnt][j] = (prpow1[prCnt][j-1] * ans[i]) % MOD;
}
for(int j = 1;j <= upSQt;j++){
prpow2[prCnt][j] = (prpow2[prCnt][j-1] * prpow1[prCnt][upSQt]) % MOD;
}
}
}
int lst = 0,now = 0;
ll secondval = 1;
for(int pri = 1;pri <= prCnt;pri++){
const int pr = prime[pri];
if(1ll * i * pr > up)break;
notp[i * pr] = true;
while(now < pr - lst){
now++;
p[now] = (p[now-1] * ans[i]) % MOD;
}
secondval = (secondval * p[pr - lst]) % MOD;
ans[i * pr] = (GetPow(pri,i,upSQt) * secondval) % MOD;
if(i % pr == 0)break;
lst = pr;
}
ret ^= (ans[i] + deltaval) % MOD;
}
return ret;
}
ll n;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>deltaval;
cout<<GetPrime(n)<<endl;
return not(Akano loves pure__Elysia);
}
Comments NOTHING