口胡记录
偶尔口胡一些题时,觉得有意思的会放在这里。
[XXI Open Cup, Grand Prix of Beijing H Nonsense]
solution
题面:给定
做法:设
讲一下
想办法表示原式,注意到
以上推导用到了
于是
update by 2021.8.4:刚刚散步的时候想了一种比较合理的做法。
我们想把二项式系数写成二项式定理然后提取出系数,这样可以等比数列求和。
即
那么
我们先给右边做一些化简
然后把不好处理的分母丢到左边,就有
和左边分子一一比对,于是就得到了
很明显我们能知道,右边只有在边界的时候,即
而
是一种经典的分母范德蒙德卷积,等于
把
综上所述,我们用了两种方法得到了这条递推式,所以要怎么优化啊?
update by 2021.8.13:突然发现最终式是个分式,所以是不是可以二元的线性递推了啊。感觉就是把纯数列转成矩阵数列就可以了,所以就能两个
[Scholomance Academy]
solution
题面:
给定
做法:这题是在吃沈阳站瓜的时候看见的,原本是沈阳站的题,现在是牛客多校的题。不过看到了就做做吧。
注意到
我们知道
其中第二步到第三步是枚举指数,然后利用隔板法算出
于是我们重新看回
前面的
后面是比较经典的二项式系数固定上系数的求和,具体做法可见我博客里的
于是进一步化简,即
这就是二项式展开形式了,所以
那么我们就求出了
是个分式,显然可以线性递推了。看起来复杂度是
[?]
solution
题面:有
做法:军训完在 u 群看到的,想了一下。
注意到当一个点
于是我们枚举这样的点
[?]
solution
题面:有
做法:每次口胡的题好像都是在 u 群看到的,emmm。
考虑从最小的情况开始扩展。对每一种状态记录最小数开始的连续长度与第二和第三段的位置,分别设为
[USTC 数分课后习题]
solution
题面:
求证:发现可以凑出伯努利不等式的形式。
若
若
综上所述,得证。
[USTC 数分 B 期末考题]
solution
题面:设
求证:对所有的
做法:考虑反证法,假设存在
于是根据条件,有
再推导一波,
于是
[?]
solution
题面:求
求证:先走两步试试!
先求一次看看效果,显然有
再走一步!
发现每一项所乘的多项式次数都很小,直接同时对两边求
代入
求出前几项,后面递推即可。
[PKU 数分课后作业?]
solution
求证:数列
证明:设
注意到
[?]
solution
求:
解:其实这题好像不管咋做都好复杂啊。首先有个经典暴力的
有道经典的题的分子是
然后再对另一个进行差差不多的变化,即
于是将这些东西代入,有
搞定!
[?]
solution
设
求证:
做法:u群有人问的,完全推不动式子,推一次感受一下好了。
直接开算!( 开抄 EI
而
接下来我就不可能想到了,感觉缺少一些积累,所以只能看 EI 的做法学习了。
发现
然后注意到上面一串
然后卷积一下,提出那一部分,即
然后再加入最后一层
然后就一步步来提取系数,即
得证了捏。