偶尔口胡一些题时,觉得有意思的会放在这里。

[XXI Open Cup, Grand Prix of Beijing H Nonsense]

solution

题面:给定 组询问 ,求 modulo

做法:设 ​。暂时只会 ​ 的暴力,听 EI 说有 ​ 的做法?(假设 ​ 同阶)

讲一下 的暴力。

想办法表示原式,注意到 的指数与 的指数和为 。于是构造

以上推导用到了

于是 预处理就可以 ​ 回答了。

update by 2021.8.4:刚刚散步的时候想了一种比较合理的做法。

我们想把二项式系数写成二项式定理然后提取出系数,这样可以等比数列求和。

那么

我们先给右边做一些化简

然后把不好处理的分母丢到左边,就有

和左边分子一一比对,于是就得到了

很明显我们能知道,右边只有在边界的时候,即 的时候才会有值,其余时候都为零。平凡地,我们可以写出与之前一样的递推式。同样在 时由于左边系数为零而无法递推求,于是仍然跟之前一样的方法,我们转为原来的 直接求,即

是一种经典的分母范德蒙德卷积,等于 ​。证明的话,可以考虑 gf 去推导,也随便考虑一种组合意义,比如

看成从 个物品中取 个,而前者则是我先在 个物品中挑选一个,然后在这个物品左边选 个,右边选 个。而这两者是等价的,因为你从 个物品中取 个,一定存在一个物品,使得左边有 个,右边有 个,这说明后者小于等于前者。而另一方面,前者的选法是唯一的,因为 ​​ 是定值,于是前者小于等于后者。于是得证。

综上所述,我们用了两种方法得到了这条递推式,所以要怎么优化啊?

update by 2021.8.13:突然发现最终式是个分式,所以是不是可以二元的线性递推了啊。感觉就是把纯数列转成矩阵数列就可以了,所以就能两个 了?

[Scholomance Academy]

solution

题面:

给定 ​, 为互不相同的质数,求 ​​ modulo ​​​。

做法:这题是在吃沈阳站瓜的时候看见的,原本是沈阳站的题,现在是牛客多校的题。不过看到了就做做吧。

注意到 ​ 为互不相同的质数,于是 ​​​。​

我们知道 ​​​ 卷积保证了函数的积性,显然的是 ​​,于是 ​​ ​依然是一个积性函数。而且 ​ 是容易求出的,即

其中第二步到第三步是枚举指数,然后利用隔板法算出 的值。

于是我们重新看回 ,容易利用积性进行改写,即

前面的 是不容易直接处理的,容易想到构造 ​,再进行一些化简,即

后面是比较经典的二项式系数固定上系数的求和,具体做法可见我博客里的 ​ 总结的第一章中关于二项式系数的部分,这里不再赘述。

于是进一步化简,即

这就是二项式展开形式了,所以

那么我们就求出了 的表达式,即

是个分式,显然可以线性递推了。看起来复杂度是 ,实际上题目中限制 ,所以复杂度骤减,就轻松通过了(虽然我没写)。​

[?]

solution

题面:有 个点,标号为 间(包括 )有一条未定向的边,边权为 。现给出若干条路径起点终点 ,希望定向后使得给定路径的边权和的和最小,问最小值。

做法:军训完在 u 群看到的,想了一下。

注意到当一个点 同时连边后,那所有路径的答案都是确定的,因为方向已经确定了。

于是我们枚举这样的点 ,发现每条路径的边权和是可以 算出来的,因为方向是单调的,在我们枚举点时,改变的路径方向之和是 的。那总复杂度就是 。注意特判全部一个方向的情况。

[?]

solution

题面:有 个数,从其中选出 个数,问第 小的和。

做法:每次口胡的题好像都是在 u 群看到的,emmm。

考虑从最小的情况开始扩展。对每一种状态记录最小数开始的连续长度与第二和第三段的位置,分别设为 ,每次扩展时,一种将 向后移动一位,一种是将最小数开始的末端向后移动一位。然后将这些状态放入一个堆中就可以了。正确性可以考虑构造一棵搜索树来证明。时间复杂度

[USTC 数分课后习题]

solution

题面: 是递增数列, 有界,求证:对任意的 ,有

求证:发现可以凑出伯努利不等式的形式。

,则根据上式,数列极限小于等于 ,而 递增,则知道数列极限大于等于 。再依据夹逼定理,就有数列极限为

,则 有界说明了该数列的极限为 ,根据上式也就说明了所求数列的极限也为

综上所述,得证。

[USTC 数分 B 期末考题]

solution

题面:设 上取值为正的可微函数,且对所有的 ,有

求证:对所有的 ,有

做法:考虑反证法,假设存在 ,满足 。并不妨令

于是根据条件,有 ,即可以得到

再推导一波,

于是 之间至少有一个小于等于 ,与题设矛盾,得证。

[?]

solution

题面:求 阶导在 处的值。

求证:先走两步试试!

先求一次看看效果,显然有

再走一步!

发现每一项所乘的多项式次数都很小,直接同时对两边求 次导,有 ( 不妨令

代入 ,有

求出前几项,后面递推即可。

[PKU 数分课后作业?]

solution

求证:数列 收敛,并求其极限。

证明:设 ,考虑差分数列 ,有递推式

注意到 ,所以可以证明那一堆省略号肯定大于 ,于是差分数列的极限为 。根据 收敛准则,有 收敛。于是将递推式两边同时取极限,就得出答案。

[?]

solution

求:

解:其实这题好像不管咋做都好复杂啊。首先有个经典暴力的 ,不过有点太难算了。还是用用

有道经典的题的分子是 搞的,我们仍然考虑那个思路,于是有

然后再对另一个进行差差不多的变化,即

于是将这些东西代入,有

搞定!

[?]

solution

求证:

做法:u群有人问的,完全推不动式子,推一次感受一下好了。

直接开算!( 开抄 EI

接下来我就不可能想到了,感觉缺少一些积累,所以只能看 EI 的做法学习了。

发现

然后注意到上面一串 是个卷积,考虑分别搞出两边的东西。

然后卷积一下,提出那一部分,即

然后再加入最后一层 ,即

然后就一步步来提取系数,即

得证了捏。