AtCoder随做

其中

直接暴力计算即可。

这种数论题目都很套路，感觉没啥意思。

简单来说，注意到 \(v\le10^{10}\)，肯定是和 \(v^w\) 相关的复杂度了，其中 \(w<1\)。

首先把每个数的立方因子给除掉，则若 \(a,b>1\) 满足 \({}^3\!\!\!\sqrt{ab}\in\mathbb N\)（下称满足匹配），则其对答案的贡献为其中较大的出现次数；对 \(1\) 特殊处理即可。

显然只用质因数分解即可得到答案，考虑如何质因数分解。

除掉立方因子需要 \(O(n\pi(^3\!\!\!\sqrt v))\) 的复杂度，同时也能分解出其所有 \(\le{}^3\!\!\!\sqrt v\) 的因子，以及剩余部分。

考虑剩余部分 \(w\) 不会有超过 \(2\) 个质因子，且均 \(>{}^3\!\!\!\sqrt v\)，考虑分类讨论：

1. \(w=1\)。这个比较简单。
2. \(w=p\)，只用考虑 \(p\le\sqrt v\) 的质数，显然 \(p>\sqrt v\) 的部分一定无法匹配。
3. \(w=p^2\)，则可以开根找到 \(p\)。
4. \(w=pq\)，由于 \(p,q>{}^3\!\!\!\sqrt v\)，\(w\) 必定无法匹配。

然后容易直接计算答案。

总复杂度 \(O(n\pi(^3\!\!\!\sqrt v)+\sqrt v+n\log n)\)，其中 \(O(n\log n)\) 的贡献来自于 map（可以哈希表代替），\(\sqrt v\) 来自于线性筛素数（实践时可以写 bitset 埃筛）。

考虑贺题解！

AtCoder 阴间题还是不会做。

为了迎合题解，对行列转置。

枚举不可放车的行集合 \(A\)；也即，之前枚举单点的方案中，\(A\) 中每行必定存在至少一个单点，且每个单点对应的行均出现在 \(A\) 中。

考虑每个连续段。（蒯图）

即，对于每一种颜色，考虑其单独某一列上的情况。

显然这对应了一个区间的行，设为第 \(l\sim r-1\) 行。

设 \(len=r-l,p=\sum_{k\in[l,r)}[k\in A]\)。

则我们单纯计算两种贡献。

• 当 \(p\) 个格子均不被选择时，有 \(2^{len-p}\) 种选择剩余部分的方法。
• 否则，有 \(\sum_{k=1}^p(-1)^k\binom pk=-[p>0]\) 种方法。

这样子容斥，会统计入某些 \(A\) 的情况，使得其中某些行不对应存在原 \(S\) 中元素。

考虑钦定 \(A\) 一部分行 \(B\) 不对应存在原 \(S\) 中元素。

即枚举 \(B\subseteq A\)，额外带上容斥系数 \((-1)^{|B|}\)。

设 \(q=\sum_{k\in[l,r)}[k\in B]\)。

再次单纯计算两种贡献。

• 当 \(p\) 个格子均不被选择时，有 \(2^{len-p}\) 种选择剩余部分的方法。
• 否则，有 \(\sum_{k=1}^{p-q}(-1)^k\binom{p-q}k=-[p>q]\) 种方法。

于是贡献即为 \(2^{len-p}-1+[p=q]\)。

换言之，答案即为

继续贺题解。

于是考虑树形 dp。

答案柿子是积和形式，尝试运用分配律。

设 \(f_{u,p,[p=q]}\)，随便对中间元素分 \(3\) 类讨论一下即可。