Solution: P7513 「Stoi2031」兰亭序 加强版

· · 题解

巨大推式子题又何尝不是一种数学大模拟呢。

来一个不一样的，应该简单一些的做法。

首先 x^n-1=\prod_{0\leq i<n}(x-\omega_n^i)，代入 x=-1 就得到

\prod_{i=0}^{n-1}(1+\omega_n^i)=1-(-1)^n=2[2\nmid n]

所以首先 2|n 时输出 0。否则直接展开最后一层：

\prod_{0\leq x_1,\cdots,x_{t-1}<n}2^{\gcd\left(\prod_{0<i<t}x_i,n\right)}

相当于是要对 0\leq m<k 求

f(n,m)=\sum_{0\leq x_1,\cdots,x_{m}<n}\gcd\left(\prod_{1\leq i\leq m}x_i,n\right)\mod 335544322

发现 335544322=2\times 167772161，后面的是知名 NTT 模数，前面那个 2 我们到时候再处理。显然 f(n,0)=1，以下我们默认 m>0 不然会很麻烦。

显然这个式子就是 ABC245Ex，所以直接把那题方法套过来，首先跟 ABC245Ex 一样 f(n,m) 是积性的，也就是说如果 \gcd(a,b)=1 则 f(ab,m)=f(a,m)f(b,m)，证明就直接 CRT，所以我们直接把 a 用 Pollard-Rho 质因数分解一下就只用考虑怎么计算 f(p^n,m) 就行了。

算 f(p^n,m) 就是枚举一下 0\leq i<n 算出 \gcd(\prod x,p^n)=p^i 有几种情况，剩下的就是 \gcd(\prod x,p^n)=p^n 的方案数。计算 \gcd(\prod x,p^n)=p^i 的方案数也和 ABC245Ex 一样，先让每个位置随便取与 p 互质的数，然后把这 i 个 p 分到某些位置上，某个位置多分到一个 p 这个地方取数的方案数就要除以 p，这样如果数组长为 m 方案数就是 \binom{m-1+i}{i}(p-1)^mp^{m(n-1)-i}。

所以最后我们得到 f(p^n,m) 是这坨东西：

f(p^n,m)=p^{n(m+1)}+\binom{m+n-1}{m}(p-1)^mp^{m(n-1)}-(p-1)^mp^{n+m(n-1)}\sum_{i=0}^{n-1}\binom{m-1+i}{i}p^{-i}

第一项是总方案数乘上 p^n，第三项是算有多少种方案 \gcd\neq p^n，它们的贡献在第一项里被算成了 p^n 要减掉，第二项是 \gcd\neq p^n 的方案的贡献。

发现 f(p^n,m) 一定是个奇数，所以模 2 的结果算出来了！这样我们只需要解决 p_{mod}=167772161 就可以合并了，具体来说结果是偶数就加上一个 167772161 即可。

现在要先讨论 p\bmod p_{mod} 为 0 或 1 的情况，因为我们以后要算 p^{-1} 和 (p-1)^{-1}，如果出现了这种情况那么 f(p^n,m)\equiv p\pmod{p_{mod}}。

现在已经能过原版了，要解决加强版要快速算后面那个和式：

g_m=\sum_{i=0}^{n-1}\binom{m-1+i}{i}p^{-i}

直接把中间那个二项式用加法公式拆了解出 g_{m+1} 就可以得到

g_{m+1}=\frac{p}{p-1}\left(g_m-\binom{m+n-1}{m}p^{-n}\right)

发现这个东西可以直接线性递推就做完了，复杂度 \Omicron(\sqrt[4]a+(k\log(bkp_{mod}))\omega(a)+k\log p_{mod})。