HDU6438 Buy and Resell

这个题目挺有意思的，值得记录下来。和以前一道CF一样。它们都是考虑一种“不关心具体方案”时的修改，即利用式子来进行“反悔”。

HDU6439 Congruence equation

记对参数 \(m\)，这样的数列 \(\{C_k\}\) 的个数为 \(f(m)\)：

• 长度为 \(k\)
• 对某些位置限制了必须为某值，而其它位置可以在有限域 \(F_m\) 中任选
• \(\sum_{1\le i\le k}C_ix_i\equiv1\pmod m\)，其中 \(x_i\) 是自由变量，这个方程要有整数解

你要计算 \(\sum_{m=1}^nf(m)\)。

\(T\le100,k\le50,n\le10^9\)，但最多对\(10\)组数据有 \(n\ge10^6\)。

首先入手点当然是那个不定方程了，同余不用怕，多加一个系数为 \(m\) 的变量之后就变成普通不定方程了。

所以有解等价于 \(\gcd(C,m)=1\) ，\(C\) 是数列中所有数字的简记法。

但是还有一些位置已经定了值，我们不妨把它们先拉出来，把它们的 \(\gcd\) 设为 \(q\)。并且令 \(k\to\text{the number of free var }c_i\)。

其实想到到这里应该就知道自己做完了这个不难的题目了，然而我却sb了，看到 \(\gcd=1\) 还想不到反演……

下面记枚举所有数列中不定的位置求和为 \(\sum_{C}\)，实际上是 \(k\) 个求和号，那么答案就是

\[ \begin{aligned} \sum_{1\le m\le n}\sum_{C}[(C,q,m)=1] &=\sum_{1\le m\le n}\sum_{C}\sum_{d|(C,q,m)}\mu(d)\\ &=\sum_{d\le n}\mu(d)\sum_{m\le n}\sum_C[d|(C,q,m)]\\ &=\sum_{d\le n}\mu(d)[d|q]\sum_{m\le n}\left(\prod_{1\le h\le k}\sum_{1\le c_h\le m}[d|c_h]\right)\\ &=\sum_{d|q}\mu(d)\sum_{p\le \left\lfloor\large\frac nd\right\rfloor}p^k\\ \end{aligned} \]

这个式子好办，直接枚举因数，然后对于后面那个自然数幂和，暴力\(\mathcal O(k^2)\)预处理伯努利数即可。由于 \(q\le n\le 10^9\)，\(\mathcal O(k^2+k\sqrt q)\) 是可以通过的。

当然，此外还有一种情形更棘手些，对于 \(q=0\) ，也就是没有限制，\(d|0\) 是（要视为）恒成立的，也就是 \(d\) 从 \(1\to n\) 枚举。这个时候我们利用和杜教筛类似的交换和号方法可以直接得到

\[ =\sum_{1\le p\le n}p^k\sum_{dp\le n}\mu(d) \]

后面那个是 \(M\left(\left\lfloor\frac nd\right\rfloor\right)\)，可以杜教筛，因为显然杜教筛 \(M(n)\) 时其实就会求出所有的 \(M\left(\left\lfloor\frac nd\right\rfloor\right)\)。

口胡一下复杂度 \(\mathcal O(k^2+k\sqrt n+n^{2/3})\)。

HDU6440 Dream

这个构造还是有点新奇的，幸好 fz 事构造大师hhh，于是我们的方案是这样的

\[ \forall x,y:x+y=1,x\times y=\min(x,y)+1 \]

其中本来是先想出了乘法，这样对幂就有

\[ a\ne0:a^0=1,\;a^1=1\times a=2,\;a^2=3,\;\cdots,\;a^{a-1}=a,\;a^a=a\cdots \]

HDU6442 GuGu Convolution

若 \(F(x)=\mathrm{EGF}\langle A^0,A^1,A^2,\cdots\rangle(x),G(x)=\mathrm{EGF}\left\langle 0,\left(\sqrt B\right)^1,0,\left(\sqrt B\right)^3,0,\left(\sqrt B\right)^5,\cdots\right\rangle(x)\)，求 \(n(x)\) 。

比较水，但是很坑。根据 EGF 卷积，答案就是

\[ \sum_{k\text{ is odd}\atop 0\le k\le n}\binom nkA^{n-k}\left(\sqrt B\right)^{k}=\frac12[(A+\sqrt B)^n-(A-\sqrt B)^n] \]

然后显然可以快速幂，有两个坑点

• 写矩阵快速幂常数太大容易 T，原因是有很多冗余运算，对 \(0\) 运算的那种。可以改成直接做线性变换，省去矩阵操作。
• 模数任意，但是只要求 \(2\) 的逆元，写个欧拉定理很不值；有个 trick：可以全程 \(\pmod{2p}\) 然后最后换回去的答案是 \(\left\lfloor\dfrac{\rm ans}{2}\right\rfloor\)。