AGC035F Two Histograms

很猎奇的转化，但是后面的计算就很简单了。

很难发现只有下面这种情况会重复。

设钦定出现 $i$ 个情况的方案数为 $f(i)$，那么显然有：

$Ans=\sum\limits_{i=0}^{\min(n,m)}(-1)^i\times f(i)$

容易理解：

$f(i)={n\choose i}\times {m\choose i}\times i!\times (n+1)^{m-i}\times (m+1)^{n-i}$

LibreOJ β Round 4 求和

不妨设 $n<m$，那么：

$\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^m \mu^2(d)[\gcd(i,j)=d]$

提出来：

$\sum\limits_{d=1}^n\mu^2(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]$

反演：

$f(k)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m [\gcd(i,j)=k]$

$g(d)=\sum\limits_{d\mid k}f(k)=\lfloor\dfrac{n}{d}\rfloor\times\lfloor\dfrac{m}{d}\rfloor$

反演得到：

$f(k)=\sum\limits_{k\mid d}\mu(\dfrac{d}{k})\times g(d)$

所以：

$f(1)=\sum\limits_{k=1}^{n}\mu(k)\times \lfloor\dfrac{n}{k}\rfloor\times \lfloor\dfrac{m}{k}\rfloor$

带回去得到：

$\sum\limits_{d=1}^n\mu^2(d)\sum\limits_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\times \lfloor\dfrac{n}{dt}\rfloor\times\lfloor\dfrac{m}{dt}\rfloor$

设 $T=dt$ 得到：

$\sum\limits_{T=1}^n\lfloor\dfrac{n}{T}\rfloor\times \lfloor\dfrac{m}{T}\rfloor\sum\limits_{d\mid T} \mu^2(d)\times \mu(\dfrac{T}{d})$

手玩发现，当 $T$ 为平方数是后面为 $\mu(\sqrt{T})$，否则为 $0$。

那么直接预处理 $\mu$ 的前缀和，在调用的时候调用 $\sqrt{}$ 之后的值就行了。

ARC101E Ribbons on Tree

考虑 $O(n^3)$ 怎么怎么解决，设 $f_{i,j}$ 表示节点 $i$ 的子树之内有 $j$ 个没有匹配。

那么为了把 $i\to fa_i$ 这条边覆盖，就需要在 $i$ 这个子树中的节点至少有一个连接到这个子树之外的节点，所以有转移方程：

$f_{fa(x),i+j-2k}\gets f_{fa(i),i+j-2k}+f_{x,i}\times f_{fa(x),j}\times {i\choose k}\times{j\choose k}\times k!$

其中 $k$ 就是选择要匹配的节点的数量，但是这个方法很没有前途。

VJO 曾经说过，正难则反，考虑容斥出答案。

设 $F(S)$ 表示 $S$ 这个集合中的边都钦定不选的方案数，那么根据容斥原理答案就是：

$\sum\limits_{S\subseteq E}(-1)^{\lvert S\rvert}F(S)$

容易理解其实有 $S$ 这些边不被覆盖，就相当于把 $S$ 里面的边删除然后在每个剩余的连通块里面乱连。

那么对于一个大小为 $N$ 的连通块，我们记它乱连的方案数为 $g(N)$，那么显然：

$g(N)=\left\{\begin{matrix} 0 & N\ \text{is odd.} \\ N\times(N-2)\times\cdots\times3\times 1 & \text{OtherWise.}\end{matrix}\right.$

设 $f_{x,i}$ 表示在以 $x$ 为根的子树里，$i$ 所在的连通块的大小，那么有转移方程：

$f_{fa(x),i+j}\gets f_{fa(x),i+j}+f_{x,i}\times f_{fa(x),j}$

$f_{fa(x),i}\gets f_{fa(x),i}-f_{fa(x),i}\times f_{x,j}\times g(j)$

容易理解上面的转移分别代表 $fa(x)$ 和 $x$ 在一个连通块和 $fa(x)$ 和 $x$ 在两个连通块的情况。

最后的答案为 $\sum\limits_{i=1}^n f_{1,i}\times g(i)$，时间复杂度为 $O(n^2)$。

CF961G Partitions

一直想做一直没做，原因是太难了而且上一次在哪里研究多项式科技耽误了很多时间。

把权值为 $w_{i}$ 的物品看作 $w_{i}$ 个权值为 $1$ 的物品，对于 $\lvert S\rvert$ 的可以看作对 $S$ 中所有的元素都贡献了 $1$。

那么对于自己给自己的贡献，显然是 $\begin{Bmatrix} n\\ k\end{Bmatrix}$。

对于别人给自己的贡献显然是 $\begin{Bmatrix} n-1\\ k\end{Bmatrix}$。

所以答案为：

$\begin{aligned} (\begin{Bmatrix} n\\ k\end{Bmatrix}+(n-1)\times \begin{Bmatrix} n-1\\ k \end{Bmatrix})\times \sum\limits_{i=1}^n w_{i} \end{aligned}$

时间复杂度为 $O(n\log V)$，另外斯特林数用通项公式处理。