笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

「划水」CF1322C Instant Noodles

posted on 2020-05-22 23:38:25 | under 题解 |

看到「和」与 $\gcd$ ,就会有一个比较 trivial 的想法,即

$$ \begin{aligned} &\gcd(x_1,x_2)=\gcd(x_1,x_2-x_1)\\ \to&\gcd(x_1,x_2,x_3,\cdots,x_k)=\gcd(x_1,x_2,x_3\cdots,x_k-x_1-x_2-x_3-\ldots) \end{aligned} $$

这一点可以用 $\gcd$ 的传(结)递(合)性(律)来证明。

然后一个比较直接的想法就是,考虑左边的点会怎么产生贡献。不难发现如果两个左部的点 $x,y$ 满足 $N(x)\cap N(y)=\emptyset$ ,那么同时选这两个的所有贡献都可以忽略。但是问题就出在 $\mathrm{card}\left( N(x)\cap N(y)\right)>0$ 的情况。这个时候很难去除交集的贡献。

但是如果将目光放到右部,就会发现关于 $\gcd$ 的那个式子依旧满足,但是此时要换成如果与两个右部点 $x',y'$ 分别连通的左部点集合 $M(x'),M(y')$ 存在交集,那么就可以直接去除掉这一部分,因为这部分的 gcd 一定是多个 $c_i$ 的和的形式。

发现从右部入手和从左部入手本质上没有什么不同,但不同就不同在有关右部的集合运算可以方便加减以及计算贡献,但是左部不行。因为本质上左部提供关系,右部提供权值。所以从右部考虑方便是显然的结论。

但是需要注意一个小点。$\gcd(x,x)=x$,但是按照上述方式会算成 $\gcd(x,x)=0$ 。所以需要 hash 一下去判一下 $M(x')=M(y')$ 的 $(x',y')$,比较方便的方式就是直接合并两者。

模数 P 可以取 $10^9+7$,Base 可以取 131。事实证明没有卡单哈希。如果 T 掉了,可以考虑将 iostream 换成 cstdio