_nekko_

编辑于 2020-03-09 16:57

【题解】牛客小白月赛14 精

~~施工中~~

A. 简单计数

普通做法

考虑矩阵二项式：

$\begin{aligned} & (A-I)^k = \sum_{i=0}^{k}{k \choose i} A^i (-I)^{k-i} \\ \Rightarrow &((A-I)^k)_{0,0}=\sum_{i=0}^{k} {k \choose i} (-1)^{k-i} n^{\max(0,i-1)} \end{aligned}$

则有：

$\begin{aligned} &\sum_{i=0}^{k} {k \choose i} (-1)^{k-i} n^{\max(0,i-1)} \\ =&\sum_{i=0}^{k} {k \choose i} (-1)^{k-i} \frac{n^i}{n}[i \ge 1] \\ =&\frac{1}{n}\left(-(-1)^{k}+\sum_{i=0}^{k} {k \choose i}(-1)^{k-i}n^i \right) + (-1)^k \\ =&\frac{(n-1)^k-(-1)^k+n(-1)^k}{n} \\ =&\frac{(n-1)^k+(n-1)(-1)^k}{n} \\ \end{aligned}$

降智严重的做法

构造矩阵 $A_{i,j}=1$ ，那么对于矩阵 $B=A-I$ ，有 $(B^k)_{0,0}$ 就是答案

可以发现它是一个循环矩阵，因此可以只用第一行来表示，设 $a_0=0,a_{1 \sim n-1}=1$ ，那么它在模 $n$ 意义下的 $k$ 次幂的 $a_0$ 即为答案

进一步可以发现， $a_{1 \sim n-1}$ 是相同的，因为它们的图论意义下是完全图上的本质相同点

于是可以只用 $(a_0,a_1)$ 来表示

那么循环卷积一次相当于：

$b'_k=\sum_{i+j \equiv k \pmod {n}} b_ia_j$

对于 $b'_0$ ，有：

$b'_0=\sum_{i=0}^{n-1}b_ia_{(n-i) \bmod n}=b_0a_0+\sum_{i=1}^{n-1}b_ia_{n-i}=b_0a_0+(n-1)b_1a_1$

对于 $b'_1$ ，有：

$b'_1=\sum_{i=0}^{n-1}b_ia_{(n-i+1) \bmod n}=b_0a_1+b_1a_0+\sum_{i=2}^{n-1}b_ia_{n-i+1}=b_0a_1+b_1a_0+(n-2)b_1a_1$

整理可得：

$\begin{cases} b_0'=(n-1)b_1 \\ b_1'=b_0+(n-2)b_1 \end{cases}$

那么只需要维护 $b'_0$ 即可，因为 $b'_1=b_0+\frac{(n-2)b'_0}{n-1}$

设 $c_k=b_0'$ ，则：

$c_k=(n-1)(c_{k-2}+\frac{n-2}{n-1}c_{k-1})=(n-1)c_{k-2}+(n-2)c_{k-1}$

其中 $c_0=1,c_1=0$ ，设 $a=n-2,b=n-1$ ，由于 $c_k=ac_{k-1}+ac_{k-2}$ ，可以发现它是一个二阶常系数齐次递推

设 $x^2=(n-2)x+(n-1)$ ，则：

$\begin{aligned} x =&\frac{(n-2) \pm \sqrt{(n-2)^2+4(n-1)}}{2} \\ =&\frac{(n-2) \pm \sqrt{n^2-4n+4+4n-4}}{2} \\ =&\frac{(n-2) \pm n}{2} \\ \in &\{ n-1, -1 \} \end{aligned}$

由于 $n \ge 1$ ，所以 $n-1 \not= -1$ ，因此有两个不同的根

于是有：

$c_k=A (n-1)^k+B(-1)^k$

由于 $c_0=1,c_1=0$ ，可以得到：

$\begin{cases} 1=A(n-1)^0+B(-1)^0=A+B \\ 0=A(n-1)-B \\ \end{cases}$

因此：

$\begin{cases} A=\frac{1}{n} \\ B=1-\frac{1}{n}=\frac{n-1}{n} \end{cases}$

因此：

$c_k=\frac{(n-1)^k+(n-1)(-1)^k}{n}$

B. 投硬币

显然答案就是：

$\sum_{i=k}^{n} {n \choose i} p^{i}(1-p)^{n-i}$

C. 植树造林

也就是问你有几个中位数，也就是 $1+[2|n]$

D. 签到题I

排序后第 $k$ 个数

E. 等比数列三角形

标程被打爆了……

就是形如 $(x,kx,k^2x)$ 的三角形个数

只需要满足：

$x+kx > k^2x$

也就是：

$k^2 - k - 1 < 0 \Rightarrow k \in \left(\frac{1-\sqrt{5}}{2}, \frac{1+\sqrt{5}}{2} \right) \Rightarrow k \in \left[1, \frac{1+\sqrt{5}}{2}\right)$

设 $k=\frac{p}{q}$ ，其中 $\gcd(p,q)=1$ ，且 $q^2|x$

$\begin{aligned} &\sum_{x=1}^{n} \sum_{q^2|x} \sum_{p=q}^{\left\lfloor q\frac{1+\sqrt{5}}{2} \right\rfloor} [\gcd(p,q)=1] \cdot f(x,\frac{p}{q}x,\frac{p^2}{q^2}x) \\ =&\sum_{q=1}^{\sqrt{n}} \sum_{q^2|x} \sum_{p=q}^{\left\lfloor q\frac{1+\sqrt{5}}{2} \right\rfloor} [\gcd(p,q)=1] \cdot f(x,\frac{p}{q}x,\frac{p^2}{q^2}x) \\ =&\sum_{q=1}^{\sqrt{n}}\sum_{i=1}^{\left\lfloor\frac{n}{q^2}\right\rfloor} \sum_{p=q}^{\left\lfloor q\frac{1+\sqrt{5}}{2} \right\rfloor} [\gcd(p,q)=1] \cdot [p^2i \le n] \\ =&\sum_{q=1}^{\sqrt{n}}\sum_{p=q}^{\left\lfloor q\frac{1+\sqrt{5}}{2} \right\rfloor} [\gcd(p,q)=1] \left\lfloor\frac{n}{\max(p^2,q^2)}\right\rfloor \\ =&\sum_{q=1}^{\sqrt{n}}\sum_{p=q}^{\left\lfloor q\frac{1+\sqrt{5}}{2} \right\rfloor} [\gcd(p,q)=1] \left\lfloor\frac{n}{p^2}\right\rfloor \\ \end{aligned}$

由于 $p \le \sqrt{n}\frac{1+\sqrt{5}}{2}$ ，且 $q \le \sqrt{n}$ ，那么预处理 $\gcd(p,q)$ 的时间复杂度就是 $O(n)$ 级别得了

那么这个暴力的时间复杂度就是：

$\sum_{i=1}^{\sqrt{n}} \frac{\sqrt{5}-1}{2}i \sim \frac{\sqrt{5}-1}{4}n$

~~恭喜获得一个常数比 1 小的算法~~

~~预处理是瓶颈~~

稍作优化，可以用 $bitset$ 来存储 $\gcd=1$ 的数组，那么空间复杂度就降为了 $O(\frac{n}{8})$

然而这个做法还是挺烦的，既然都有 $[x=1]$ 了，那么肯定能通过 $\mu$ 来使得时间复杂度降下去

设 $e=\frac{1+\sqrt{5}}{2}$ ，显然答案就是：

$\begin{aligned} &\sum_{p=1}^{\sqrt{n}} \left\lfloor \frac{n}{p^2} \right\rfloor \sum_{q=\left\lceil\frac{p}{e} \right\rceil}^{p} [\gcd(p,q)=1] \\ =&\sum_{p=1}^{\sqrt{n}} \left\lfloor \frac{n}{p^2} \right\rfloor \left(\phi(p) - S\left(\left\lfloor \frac{p}{e} \right\rfloor,p\right) \right)\\ \end{aligned}$

其中：

$\begin{aligned} S(n,p) =&\sum_{i=1}^{n} [\gcd(i,p)=1] \\ =&\sum_{d|p}\mu(d)\left\lfloor \frac{n}{d} \right\rfloor \end{aligned}$

那么暴力模拟这个过程，时间复杂度为：

$\sum_{i=1}^{\sqrt{n}} \sigma_0(i) \sim \sqrt{n} \log n$

F. 乐色王传奇

算法1

我会 $\bf dfs$ ！暴力枚举出每一种可能的情况，将最大值加起来，最后除以 $N^N$ 即可。

复杂度 $O(N^N)$ ，期望得分 $10$ 分。

算法2

不如我们统计每个数对上面那个总答案的贡献，最后把所有的贡献加起来？

我们发现这个贡献即是 $( \ V_{ij} \times$ 以 $V_{ij}$ 为最大值的情况数 $\ )$ 。

如果有值相同呢？那我们这样规定即可：值为第一关键字，行数为第二关键字，列数为第三关键字。

比如这个表是这样的：

那么 $V_{11} < V_{12} < V_{21} < V_{22}$ 。我们发现这么做不会影响答案，并且可以将每个数字的贡献统计得不重不漏。

所以这个情况数到底是多少呢？

对于 $V_{xy}$ 来说，我们要求从其他行里选出来的数都严格小于它。

所以情况数是 $\prod \limits_{i=1,i \ne x}^{N} \ \ ( \ \sum \limits_{j=1}^{N} \ (V_{ij} < V_{xy} ? 1:0) \ )$

对于每个数字， $\bf for$ 一遍统计即可，复杂度 $O(N^4)$ 。期望得分 $20$ 分。

算法3

有一些奇怪的 $N^3 \log N$ 算法存在。我忘了，但是肯定有。期望得分 $40$ 分。

算法4

首先我们将每行的排序。

我们发现对于每一行我们可以一起算。

具体来说就是对于每个其他的行维护一个指针（共 $N-1$ 个），然后在维护一个当前行的指针 $\bf tmp$ 。

每当 $\bf tmp++$ 时，我们扫一遍所有其它行的指针，如果其它行指针所指的元素小于 $\bf tmp$ 所指的元素，令其它行指针 $\bf ++$ ，并且维护那个式子即可。

由于我们一共有 $N^2$ 个元素，所以我们要扫 $N^2$ 次。

故复杂度为 $O(N^2 \times N)=O(N^3)$ （瓶颈就在这）。期望得分 $70$ 分。

算法5

那我们为什么不将 $N^2$ 个值一起算出来呢？

细想一下其实是可以的。

我们先将所有元素放一起排序，然后每个行维护一个指针（共 $N$ 个）。然后跟算法 $4$ 的思路一样。

注意下细节即可，复杂度 $O(N^2 \log N)$ ，期望得分 $100$ 分。

G. many sum

for(int i = 1 ; i <= n ; ++ i) {
    for(int j = i ; j <= n ; j += i) {
        b[j] += a[i];
    }
}

此时已经可以通过此题了，但如果能做 $n=2 \times 10^7$ 岂不是更爽

考察这个过程，相当于做了一次高维前缀和，那么就模拟一遍即可

H. 图上计数

这题为啥没人做啊

对于操作一，相当于把子树给缩起来

对于操作二，相当于求子树第 $k$ 大， $dfs$ 序一下就好了，离线后树状数组就可以了

I. 有毒的玻璃球

可以发现 $\sigma_k$ 是一个积性函数，那么线性筛出来就行了

J. J.I

重新说一遍题意

给定一个森林，在其中连尽可能多的边使得仍然是一个二分图（显然森林就是一个二分图）

首先对于每一棵树，可以把它看成一个pair，即分成左右两个点集 $(a,b)$

也就是说有一些 $(a_i,b_i)$ ，可以对于一个 $(a_i,b_i)$ 变成 $(b_i,a_i)$ ，要求最大化 $(\sum a_i)(\sum b_i)-m$

其中 $m$ 是森林中的边的个数

如果你做过poj 1112的话，你会发现这是个背包裸题

直接 $bitset$ 压位跑一下就行了

2024最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(2) 回帖

加载中...

话题同步到我的动态回帖