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$ 压位跑一下就行了

全部评论

推荐最新楼层

zfwserwr

腾讯_微信_后台研发工程师

，请问后面的n在矩阵A中表示什么含义？为什么n的次数是max(0, i - 1), 而不是i呢？谢谢。@nekkko

送花回复

发布于 2019-05-13 11:25

_nekko_

楼主

清华大学数学类

upd：等比数列三角形那个题可以优化到sqrtn loglogn，题解在：https://loj.ac/article/1679

送花回复

发布于 2019-06-02 14:11

秋招专场

校招火热招聘中

官网直投

勇敢的查理斯正在卷

05-25 09:40

软件测试

软件测试工程师工资待遇大概是什么水平？

跟学历有关，211，985的 一年工作经验，6000起步，二年8000起步普通高校，一年4000多，二年的话，一般7000左右当然，如果你的能力很强，可以带队，10000也是有可能的

点赞评论收藏

屋顶的闪闪星光

05-26 18:57

全栈开发

国企方向就业的性价比之王——雄安新区

今天早上闲来无事统计了一下找我私聊过的朋友中收到的软件技术类岗位offer： 电信、移动、联通、铁塔、星网都已经入驻并且招聘软件技术人员，像联通产互、中移集成、中电信数字城市、铁塔智联、星网研究院等，中国星网总部也即将迁入。 六大行中，交行、农行、建行都在雄安设立了科创中心，在招聘软件技术人员。 除了上面这些招聘正常软件技术产研人员的单位，其它还有一些非IT相关单位但仍然有信息科技类工作岗位的： 有政策有产业，银行的业务就会有体量，因此各银行都会设置雄安分行，中行、工行的雄安分行甚至是总行直属。 在国务院直属九十多家央企中，雄安新区目前有4家央企总部（中国星网、中国中化、中国华能...

点赞评论收藏

04-19 21:12

烦请各位赏个脸，帮我看看为什么简历投啥挂啥

点赞评论收藏

Bloomer

05-17 17:02

哈尔滨工业大学（威海）自动化类

老哥们我这样能找到暑期实习吗

😭😭😭什么项目都没有会有小厂要我实习吗，想找嵌入式软件的实习 #实习#

点赞评论收藏

努力再努力__

05-28 17:15

北京邮电大学电子信息类

Java后端日常实习offer选择美团丨猿辅导

猿辅导 Java后端日常实习 800一天

点赞评论收藏

点赞收藏评论

全站热榜

正在热议