麻将.jpg
观察牌型和计算方法可知，选择一个杠与选择一个面子对于牌型的贡献是等价的
而选择一个杠的答案一定没有选择一个刻子优，因此是没有任何意义的
除去 "七对子" "国士无双" 的特殊情况后，此外的情况就是选择 4个面子 + 1个雀头
容易想到对于每个花色dp得到选择 \(i\) 个面子 \(j\) 个雀头的答案，然后背包合并
为了 \(dp\) 顺子的情况，可以存储前面两个位置作为顺子头的个数
令 \(dp_{i,j,a,b}\) 表示当前选了 \(i\) 个面子， \(j\) 个雀头，上两个位置选了 \(a\) 个顺子，上一个位置选了 \(b\) 个顺子
暴力维护dp即可
1 | const int INF=1e9+10; |
可以发现更新操作就是 \(\text{LCT}\) 的 \(\text{Access}\) 操作，这个操作复杂度是 \(O(n\log n)\) 的
因此，考虑对于每次的 \(\text{Access}\) 操作，维护每个点到根的路径上不同的权值个数
每次 \(\text{Access}\) 操作只设计到合并两个链/断开一条链两种操作，可以通过线段树维护子树修改
那么修改的复杂度就是 \(O(n\log^2 n)\)
对于二操作，自己模拟一下就知道，就是两个点的答案-2 \(\cdot \text{LCA}\) 答案+1
实现上有一些细节，就是更新的子树根节点是需要查询得到的
1 | const int N=1e5+10; |
注意到到达关系是相互的，因此可以把能够互相到达的点放到同一集合中
因此只需要考虑最简单的到达情况，发现实际上当一个点有两条同色入边时，可以将这两条边对应的点合并
对于每个集合，维护一个颜色出边的集合，可以用 \(\text{std::map}\) 实现，每次合并两个点用并查集处理集合关系
然后用启发式合并的方式维护集合的边，即可做到 \(O(m\log^2 m)\)
用线段树合并的方式维护同样的东西即可做到 \(O(m\log k)\)
1 | #include<bits/stdc++.h> |
直接枚举每一位求值显然至少是 \(O(n|S|)\) 的，为了减少计算次数，考虑对于 \(n\) 个不同数组的情况归纳出一些通用情况
对于一个数组，考虑计算答案 \(\ge A_i\) 的方案数，那么有一部分数 \(\ge A_i\)
直接状压 \(\ge A_i\) 的数的集合，对于的数不同二进制表示就可以得到 \(2^m\) 种不同的状态
在计算时，只需要考虑是否 \(\ge A_i\) ，分为两种值， \(O(1)\) 合并即可
预处理出每个二进制对应的值，然后对于每个 \(A_i\) 计算答案即可
复杂度为 \(O(|S|2^m+nm\log m)\)
1 | #include<bits/stdc++.h> |
置换同构计数真是令人头大，感觉依然不是特别懂
\[ \ \]
设按照题意生成的 \(n\) 个节点有标号有根树族为 \(\mathcal{T}_n\) ，对于某种树形 \(T\) 的生成方案数为 \(c(T)\)
则答案显然是 \(\cfrac{\sum _{T\in \mathcal{T}_n} c^k(T)}{(n-1)!^k}\)
\(k\) 的量级意味着我们无法完成有关 \(c^k(T)\) 的展开，因此要在最开始的计算中就将 \(k\) 这个幂次加入
为此定义 \(F_{i,n}=\sum _{T\in \mathcal{T}_n} c^{ik}(T)\)
则我们要计算的答案就是 \(\cfrac{F_{1,n}}{(n-1)!^k}\)
容易发现有意义的 \(F_{i,j}\) 规模为 \(O(\sum \sum [ij\leq n])=O(n\ln n)\)
关于为什么 \(F_{i,n}\) 会有第一维，会在下面出现
ps: 我的两个维度好像和别人是反的
考虑递推计算 \(F_{i,n}\)
容易发现对于任意一个 \(F_{i,n}\) 的计算只需要令 \(k\rightarrow ik\)
为了简化描述，我们先以计算 \(F_{1,...}\) 为例
对于同构树计数，子树的叠加是无序的背包问题，树形之间存在着置换同构
而每棵子树的编号之间可以任意归并，因此需要 \(\text{EGF}\) 的背包合并每棵子树
显然同构仅出现在同种大小的子树中，因此可以对于不同大小的子树分离
假设对于大小为 \(n\) 的子树，出现了 \(m\) 种不同的树形 \(T_1,T_2,\ldots T_m\) ，每种出现了 \(a_i\) 个
则答案应该为 \(\displaystyle \sum_{T_i\ne T_j} \frac{1}{(n!)^m}\prod \frac{c^{a_ik}(T_i)}{(a_i!)^k}\)
其中 \((a_i!)^k\) 除去同构树之间无排列序的方案数
普通的背包计数难以处理 \(T_i\ne T_j\) 的限制
因此考虑用 \(\text{Burnside}\) 引理解决置换同构问题
同构出现于 \(m\) 棵树之间，因此我们置换群为对于 \(m\) 的排列置换群
显然任意一个排列置换的的结果是若干个置换环，环上的树树形相同
则对于一个置换 \(f\) ，设其生成了大小分别为 \(b_1,b_2,\ldots, b_m\) 的置换环
理想情况下其不动点的式子计算如下
\(\displaystyle \text{fix}(f)=\frac{(n\sum b_i)!}{(n!)^{\sum b_i}}\cdot \frac{F_{b_i,n}}{(b_i!)^k}\)
（这就是为什么要给 \(F\) 添加第一维）
其中 \(\cfrac{(n\sum b_i)!}{(n!)^{\sum b_i}}\) 处理了 \(\sum b_i\) 棵树的点编号，实际上这两个权值可以在计算的最后加入，因此下面忽略掉
而实际上，在不动点中直接加入 \(\cfrac{1}{(b_i!)^k}\) 是错的
原因在于让这样的 置换环权值 带入 \(\text{Burnside}\) 引理之后
最终的 同构类权值 并不是我们想要的 \(\cfrac{1}{(a_i!)^k}\)
考虑 待定求解 一个置换环系数的 \(\text{EGF}\) ，设其为 \(A(x)\)
相较于上面的枚举 \(f\) 的式子，这里的计算中系数还需要考虑对于每种 \(b_i\) ，等价的置换 \(f\) 个数
这同样需要对于每棵子树的 \(\text{EGF}\) 合并，系数为 \(\cfrac{1}{b_i!}\)
而一个环上的点存在一个环排列 \((b_i-1)!\) ，两者合并即 \(\cfrac{1}{b_i}\)
注意这一部分并未被加入 \(A(x)\) 中
然而这也恰好使得 \(\text{Burnside}\) 引理的系数 \(\frac{1}{m!}\) 和置换元素的 \(\text{EGF}\) 系数相抵消
不妨设添加环系数 \(\text{EGF}\) 的变换为 \(\hat A_i=\cfrac{A_i}{i}\)
所以，则最终的计算中 \(\text{Burnside}\) 引理的答案就是 \(\text{exp}(\hat A(x))\)
我们希望最终一个 合法的同构类 的权值为 \(\cfrac{1}{(a_i!)^k}\)
而容易发现实际上 最终的同构类 是由我们初始枚举的置换环 的 \(\text{exp}\)
因此 \(\cfrac{1}{a_i!}\) 应当是置换环系数经过环元素 \(\text{exp}\) 叠加的结果
设 \(B(x)=\cfrac{x^i}{(i!)^k},C_i=\cfrac{A_i}{F_{n,i}}\)
则 \(B(x)=\text{exp}(\hat C(x))\) ，对于 \(B(x)\) 取 \(\ln\) 得到 \(\hat C(x)\)
加入系数得到我们前面所待定的 \(A(x)\) ，即可进行最后的 \(\text{exp}(\hat A(x))\) 计算
ps:
你会发现可以直接忽略环 \(\text{EGF}\) 变换，全程只有 \(\hat C(x),\hat A(x)\) ，在过渡中这个变换的系数直接消失了
在这里提到这个系数是为了避免不必要的误解，同时也强调其他时候使用 \(\text{Burnside}\) 引理需要添加这个系数
倒序枚举 \(F_{i,j}\) 的 \(i\) ，正序枚举大小 \(j\) ，边界条件自然是 \(F_{i,1}=1\)
确定了一个 \(i\) 后，就可以预处理 \(\ln\) 求出置换环系数，这里有 \(\frac{n}{i}\) 个
按照每个 \(i\) ，上面式子中的 \(k\rightarrow ik\)
按照 \(j\) 从小到大计算 \(F_{i,j}\) ，每次得到 \(F_{i,j}\) 之后
计算关于大小为 \(j\) 的树的背包系数，这里系数的个数为 \(l=\frac{n}{ij}\)
将先前的系数补上 \(F_{d,j}\) ，再做 \(\text{exp}\) ，最后把前面扔掉的 \(\cfrac{1}{(n!)^{\sum a_i}}\) 补上，( \((n\sum a_i)!\) 直接作为后面 \(\text{EGF}\) 合并的系数）
然后将它补进前面累和的背包里，就能得到这一项的值
注意前面算的式子都是计算儿子的，最后还要加上自己的大小1
当然，计算 \(\text{exp},\ln\) 需要下面的帮助
\(F(x)=\text{exp}(G(x))\)
\(F'(x)=\text{exp}(G(x))G'(x)\)
\(F'(x)=F(x)G'(x)\)
先计算出 \(G'(x)\) ，然后 \(O(n^2)\) 依次得到 \(F'(x)\) 的第 \(i\) 项，就能知道 \(F(x)\) 的第 \(i+1\) 项
\(F(x)=\ln G(x)\)
\(F'(x)G(x)=G'(x)\)
边界 \([x^0]G(x)=1,[x^0]F(x)=0\)
暴力推 \(F'(x)\) 的每一项即可
上面的计算时，每次求得一个 \(\hat A(x)\) ，都做一次 \(\text{exp}\) ，然后背包合并
但是实际上，我们可以先将 \(\hat A(x)\) 放在一起，然后一起做 \(\text{exp}\)
具体的，每次得到 \(F_{i,j}\) 之和，我们就可以确定 \(\sum \hat A(x)\) 的第 \(j\) 项
那么在维护 \(\sum \hat A(x)\) 的同时，也依次递推 \(\text{exp}(\sum \hat A(x))\) 的 \(j\) 项
这样不仅去掉的背包的过程，也少了很多次 \(\text{exp}\)
\[ \ \]
相对于 \(\text{exp}\) ，求 \(\ln\) 的复杂度可以忽略
而 \(\text{exp}\) 每次大小是 \(\frac{n}{ij}\) ，即 \(O(\sum \sum \cfrac{n^2}{i^2j^2})=O(n^2)\)
最后的复杂度反而在于背包合并 \(\text{EGF}\) ，为 \(O(n^2\ln n)\)
同步求 \(\text{exp}\) 的复杂度为 \(O((\cfrac{n}{i})^2)=O(n^2)\)
Code1:
1 | const int N=2010; |
1 | #include<cstdio> |
吐槽：实际上套了板子之后已经比loj上的所有人都快了
但是由于新旧评测机的问题~~~，总时间就显得慢了
1 | #include<bits/stdc++.h> |
这种东西看到就给人一种
分块分块分块分块分块分块!
啊啊啊啊啊啊啊啊啊啊啊
\[\ \]
这是一个二维区间顺序对问题，对于普通的区间顺序对问题，我们有简单分块解法
预处理整块的答案，有 \(n\sqrt n\) 个数要插入预处理，也就是有 \(O(\sqrt n)\) 个区间查询
对于散点暴力求，也是 \(n\sqrt n\) 个区间查询问题
那么离线+分块就可以做到 \(O(\sqrt n)\) 插入一个数， \(O(\sqrt 1)\) 查询，并且有办法将空间实现到 \(O(n)\)
那么对于二维区间考虑部分沿用上面的思路
\[ \ \]
首先对于散块的部分，是完全一样的处理，可以 \(O(n)\) 内存实现
具体的：
散点之间可以暴力 \(for\) 答案，每次还需要一个二维区间个数查询
每次需要查询的散点又是一段区间
可以描述为 \(O(m)\) 个查询，总共查询 \(O(m\sqrt n)\) 个散点
\[ \ \]
问题在于整块部分的查询 \([p1,p2],[u,d]\)
对于同一个块内的答案，可以暴力预处理出来
\[ \ \]
而块之间，可以转化为 \([1,d]-[1,u-1]-[1,u-1]\times [u,d]\)
前面两个前缀型问题，可以用如下方法实现：
按照 \(p_i\) 从小到大插入，同时维护每个块内已经出现的个数
每次插入 \(i\) 后，对于 \(i\) 前面的块，会产生 \(O(\sqrt n)\) 对 顺序对
我们要查询的是一个块编号 \([p1,p2]\) 内块的关系，这是一个二维前缀和
可以把两个维度的前缀和分开给插入和查询
具体的，在插入时，处理 \(S_{l,r}=\sum_{i\ge l} C_{i,r}\)
查询 \([p1,p2]\) 时，就可以暴力求 \(S_{l,i}i\in[l,r]\) 的和
这样可以分摊复杂度为 \(O(n\sqrt n)\) ，并且内存为 \(O(n)\) ，常数较小
\[ \ \]
对于 \([1,u-1]\times [u,d]\) ，从左到右一段段 查询过来，每次查询块内 \([1,u-1]\) \(，[u,d]\) 个数即可
这个统计和上面的块内答案统计都需要预处理每个数在块内排名
但是也可以通过离线去掉这个步骤，避免了一个 \(O(n\sqrt n)\) 的数组
\[ \ \]
实际实现时，发现散块暴力的部分枚举起来实在太慢，所以块开大了一点，加了一点底层玄学优化
1 | #include<bits/stdc++.h> |
神题
设 \(\text{FWT}_{\oplus}(F(x))=F'(x)\)
关于 \(\text{FWT}_{\oplus}\) 的展开式子，我发现大部分人都不晓得。。。。
\([x^S]F'(x)=\sum_T(-1)^{|S\cap T|} [x^T]F(x)\)
\(F(x)=\frac{F''(x)}{2^n}\)
详细可以看这个
定义 \(\bigoplus\) 为两个多项式的异或卷积
\(\times\) 为两个多项式对应项直接相乘
\([x^S]F(x)\) 表示 \(F(x)\) 的第 \(S\) 项的系数
翻转过程是一个 \(\oplus\) 的过程，所以考虑用集合幂指数配合 \(\text{FWT}_\oplus\) 构造和求解方程
事实上问题等价于从初始状态 \(S\) 跑到 \(\empty\) 的期望次数
设从 \(S\) 到 \(\empty\) 的期望次数生成函数为 \(F(x)\) ，其中 \([x^{\empty}]F(x)=0\)
设转移函数 \(G(x),[x^{\{i\}}]G(x)=p_i\)
那么我们的方程就是 \(F(x)\bigoplus G(x)+\sum x^S+cx^{\empty}=F(x)\)
其中 \(x^S\) 表示这次转移之后答案要加一
由于直接这样转移得到的方程显然是无穷解的，因为无法保证 \([x^{\empty}]F(x)=0\)
所以我们用一个常数项 \(cx^{\empty}\) 平衡这个问题， \(c\) 现在是未知的
\(\because F(x)\bigoplus G(x)+\sum x^S+cx^{\empty}=F(x)\)
\(\therefore (F(x)\bigoplus G(x)+\sum x^S+cx^{\empty})'=F'(x)\)
\(\therefore F'(x)\times G'(x)+(\sum x^S+cx^{\empty})'=F'(x)\)
我们模拟一下 \(G'(x)\)
\([x^S]G'(x)=\sum_i(-1)^{|S\cap \{i\}|}[x^{\{i\}}]G(x)=\sum_{i\notin S}p_i-\sum_{i\in S}p_i\)
再卷一下 \((\sum x^S+cx^{\empty})'\)
\((\sum x^S)'=\sum_S\sum_T(-1)^{|S\cap T|}x^S\)
\(\because (-1)^{|S\cap T|} =\sum_{T\subset S}(-1)^|T|\cdot 2^{n-|S|}=[S=\empty]2^{n-|S|}\)
\(\therefore (\sum x^S)'=2^n x^{\empty}\)
\((cx^{\empty})'=\sum c\cdot x^S\)
然后我们带入反解 \([x^S]F'(x)\)
当 \(S=\empty\) 时,
则 \([x^S]F'(x)\cdot [x^S]G'(x)+2^n+c=[x^S]F'(x)\)
然后发现此时 \([x^S]G'(x)=1\) ，那么就意味着 \(2^n+c=0\)
解出了 \(c=-2^n\) ，但是此时我们实际上并不知道 \([x^{\empty}]F'(x)\) 的值
当 \(S\ne \empty\) 时
\([x^S]F'(x)\cdot [x^S]G'(x)+c=[x^S]F'(x）\)
\([x^S]F'(x)(1-[x^S]G'(x))=c\)
\[[x^S]F'(x)=-\frac{2^n}{1-\sum_{i\notin S}p_i+\sum_{i\in S}p_i}=-\frac{2^n}{2\sum_{i\in S}p_i}\]
我们考虑要求出 \([x^\empty]F'(x)\) 的值
由 \([x^{\empty}]F(x)=2^{-n}\cdot \sum [x^S] F'(x)=0\)
\[[x^\empty]F'(x)-\sum_{S\ne \empty}\frac{2^n}{2\sum_{i\in S}p_i}=0\]
那么我们由 \(F'(x)\) 回代得到 \([x^S]F(x)(S \ne \empty)\)
\[[x^S]F(x)=2^{-n}\cdot \sum_T(-1)^{|S\cap T|}[x^T]F'(x)\]
\[=2^{-n}([x^\empty]F'(x)+\sum_{T\ne \empty}(-1)^{|S\cap T|}[x^T]F'(x))\]
\[=\sum_{T\ne\empty}\frac{1}{2\sum_{i\in T}p_i}+2^{-n}\sum_{T\ne \empty}(-1)^{|S\cap T|}[x^T]F'(x)\]
\[=\sum_{T\ne \empty,|S\cap T|\mod 2=1} \frac{1}{\sum_{i\in T} p_i}\]
下面是一个背包，跑的同时统计一下就好了 \(|S\cap T|\) 的奇偶性就好了
然后会发现事实上并没有必要特判 \(S=\empty\) 的情况
1 | #include<cstdio> |
令 \(f_m\) 表示期望次数，显然 \(m>0,f_m=\frac{(n-m)f_m+mf_{m-1}}{n}+1\)
即 \(f_0=0,f_m=f_{m-1}+\frac{n}{m}\)
即 \(\displaystyle f_m=\sum_{i=1}^m \frac{n}{i}\)
回到原问题的 \(a_1,a_2,\ldots,a_m\) ，按照连续 \(k\) 个分段，设每段开始点 \(A_i\)
我们要求这些 \([A_i,A_i+k)\) 第一次有一个被满足的期望，这难以解决
用一个 \(\text{minmax}\) 容斥处理掉
\(\displaystyle \min\{\exists A_i合法\}=(-1)^{T+1}\sum_{T\subset S} \max\{\forall i\in T,A_i合法\}\)
这个 \(\text{max}\) 显然取决于 \(A_i\) 并的长度
令 \(dp_{i,j}\) 表示当前最大的选择点为 \(i\) ，选择的总长度为 \(j\) ，容易用前缀和优化到 \(O(n^2)\)
\[ \ \]
容易想到对于每个长度 \(\ge k\) 的连续段分别求解，然后分治 \(\text{NTT}\) 背包合并
此时我们要对于连续 \(n\) 个元素可以选择的子问题求解答案生成函数 \(F_n(x)\)
\[ \ \]
考虑此时，收尾两个段必须选择，而中间的段(个数 \(>0\) )随意选择
由等式 \(\sum {T\in S} (-1)^{|T|}=[S=\empty]\) 可知，其系数为0
观察一下我们能由这个推论得到什么
令 \(dp_{n}\) 表示顺次覆盖前 \(n\) 个元素的系数
\(dp_{k}=-1,dp_{k+1}=-dp_{k}=1\)
\(\forall i\in[k+2,2k],dp_i=0\)
\(dp_{2k+1}=-dp_{k+1}=-1\)
\(dp_{2k+2}=-dp_{2k+1}=1\)
想必睿智的你一定已经发现了， \(dp\) 数组 \(k+1\) 一循环
实际上根据这个性质的暴力 \(dp\)
可以多10pts
由于 \(dp_{k+1}=1\) ，也可以表示为 \(dp_{i}=dp_{k+1}\cdot dp_{i-k-1}\)
因此可以把连续段的前 \(k+1\) 个分裂开来，假装不连续
此时，我们可以简单描述为：
每次选择的是一个长度为 \(k+1\) 的段
可以覆盖前 \(k\) 个，系数为 \(-1\)
也可以覆盖 \(k+1\) 个，系数为 \(1\)
并且这 \(k+1\) 个段不能相交，可以相邻
根据这样的决策，计算系数可以分为两步
\(n\) 个元素选出 \(i\) 个长度为 \(k+1\) 的段，剩下的元素可以分配到这 \(i+1\) 个间隔中
方案数为 \(\displaystyle \binom{n-i(k+1)+i+1-1}{i+1-1}=\binom{n-ik}{i}\)
一开始令这些段都选择前 \(k\) 个，然后对于某一些可以额外选择最后一个，乘上 \(-x\)
由此我们列出 \(\text{OGF}\) 表达式
\(\displaystyle G_n(x)=\sum_{i=0}^{\frac{n}{k+1}} (-1)^i\binom{n-ik}{i}x^{ik}(1-x)^i\)
\(\displaystyle G_n(x)=\sum_{i=0}^{\frac{n}{k+1}} \binom{n-ik}{i}x^{ik}(x-1)^i\)
注意边界情况是最后 \(k\) 个被选的情况不会算进去，因此实际上
\(F_n(x)=G_n(x)-x^kG_n(n-k)\)
考虑如何计算 \(G_n(x)\)
我们对于所有的 \(i\) 分治，分治到区间 \([l,r]\) 时，我们维护的是
\(\displaystyle \sum_{i=l}^{r} \binom{n-ik}{i}x^{(i-l)k}(x-1)^{(i-l)}\)
这样就能保证分治时，区间内多项式长度为 \(O((r-l+1)(k+1))\)
合并时，给右区间补上 \(x^{(mid-l+1)k}(x-1)^{mid-l+1}\) 即可
因此计算 \(F_n(x)\) 和合并 \(F_n(x)\) 的复杂度均为 \(O(n\log ^2n)\)
不 \(sort\)
有80pts.jpg
代码好看就完事了
1 | #include<bits/stdc++.h> |
这自然有后缀数组和后缀自动的写法，我写的是后缀数组
现对于 \(A,B\) 两串拼接后建立 \(\text{SA}\)
对于查询的四个参数 \([s,t,l,r]\) ，在 \(\text{SA}\) 上找到能够匹配 \([l,r]\) 的 \(\text{rank}\) 区间 \([l',r']\)
这个 \([l',r']\) 就用 \(\text{SA}\) 的 \(\text{height}\) 数组上倍增即可 \(O(\log n)\) 找到
由于 \(K>n\) ，显然覆盖就是从左到右依次匹配每个 \(\text{rank}\) 在 \([l',r']\) 中的 \(i\) ，能放就放
数据范围提示我们切分写
对于每种不同的 \(r-l\) ，倍增预处理
我们将依次匹配的过程描述成一个个跳跃
对于每个 \(i\) 找到后面第一个 \(j\) 满足 \(j>i+r-l,\text{LCP}(i,j)\ge r-l+1\)
具体的，将 \(\text{SA}\) 的 \(\text{height}\) 数组按照 \(\text{height}_p\ge r-l+1\) 分成一段一段
每个连续段中的两个位置 \(\text{LCP}\ge r-l+1\)
合法的 \(i,j\) 一定出现的某个连续段中
找到每一个这样一个连续段，然后双指针得到合法的 \(i,j\) 即可
\[ \ \]
这样的跳跃关系，以及跳跃过程中的答案，可以通过倍增来维护出来
对于每个询问，可以先找到区间内第一个合法的点 \(i_0\) ，然后倍增查询答案即可
找到 \(i_0\) 可以用主席树二分出 \(\text{rank}\) 在 \([l',r']\) 内的第一个 \(i_0\ge s\) 的位置
复杂度为 \(O(50n\log n+q\log n)\)
\[ \ \]
根据数据范围，这里我们只要能够暴力跳每一个合法的 \(i\) 即可
那么像上面一样，用主席树每次找 \([l',r']\) 内第一个 \(i'> i+r-l\)
每次 \(\log n\) 跳即可，复杂度为 \(O(\frac{nq}{r-l}\log n)\)
1 | #include<bits/stdc++.h> |
很显然，这是一道有时限的提答题!!!!
但是知识点很丰富，值得一写
直接快速幂 \(19^x\) ，如果读入太大，指数可以 \(\mod \varphi(998244353)\) ,不谈...
不知道模数，但是可以看出模数很小，随便选一个答案试出模数即可(145141?)
值域非常大，就算是快速幂也显然要通过快速乘来实现，设模数为 \(P\)
把所有读入的数拿出来看，发现最相近的两个相差只有 \(2\)
意味着我们知道
\(19^x \equiv a\pmod P,19^{x+2} \equiv b \pmod P\)
很显然 \(a\cdot 19^2 \mod P=b\) ，求出 \(a\cdot 19^2-b\) ，分解质因数即可
实际实现可以用手写高精/Python
答案的生成是，求幂次的时候乘法不开long long ，即
1 | int n,s=1; scanf("%d",&n); |
出题人的tips给了，自然溢出是非定义行为，甚至有可能导致RE
所以模拟的话，实际应该这样写
1 | s=int(((unsigned)s*19))%P; |
可以发现，这个答案的序列近似于一个伪随机数列，学过 \(\text{Pollard's Rho}\) 算法就知道，
根据生日问题/生日悖论，伪随机数列期望在 \(O(\sqrt n)\) 的时间内产生一个伪循环，因此可以快速求解
1 | int s[300000]; |
判断 \([l,r]\) 内的数是否是质数，\(\text{Miller_Rabin}\) 模板
求 \([L,R]\) 内的莫比乌斯系数 \(w(n)\) ，设 \(n=\prod_1^m p_i^{c_i},c_i>0\)
\(w(n)=\left\{\begin{aligned} (-1)^m &&\nexists c_i>1,\\ 0 && \exists c_i>1\end{aligned}\right.\)
对于 \(L,R\) 达到 \(10^{18}\) 次时，考虑先用 \([1,R^{\frac{1}{3}}]\) 内的质数筛掉，那么剩下的数最多包含两个 \((R^{\frac{1}{3}},R]\) 内的质因数
可以开根号判断是否是平方数，用 \(\text{Miller_Rabin}\) 判断是否是质数
由于 \(R-L\) 与 \(R^{\frac{1}{3}}\) 同阶复杂度为 \(O(R^{\frac{1}{3}}\log R^{\frac{1}{3}})\) ，常数较大
1 | #include<bits/stdc++.h> |