前言
今天打得有点惨,特开一篇.
-
D
数学题目,考虑插板法,对于 \(i\) 个红球,存在 \(i-1\) 个缝隙供蓝球,但是注意到左右两边各有分析,最后就存在 \(i+2\) 个缝隙.对于本题,即存在 \(n-k+1\) 个缝隙.然后枚举每一个段即可.
\[\sum^k_{i=1} C^{n-k+1}_i \times C^{k-1}_{i+1} \]也许会超出答案,取模的确麻烦,所以使用杨辉三角即可.
-
E
考试的时候SB了的题目.实际上,我们只需要将 \(3\) 层图就行了,对于每一层,表示第 \(i\) 小步,然后 \(dijkstra\) 即可.
-
F
考虑最朴素的dp方法,也就是 \(dp_{i,j}=\sum\limits_{k=1}^{\frac{n}{j}} dp_{i-1,k}\).注意到数据范围,肯定会超时,不妨设计一种缝合怪dp.
我们假设用 \(g_{i,j}\) 表示 \(i+1\) 位不大于 \(j\) 的方案数,可以很自然的发现 \(i\) 越大,他越快.
接着,我们不妨把这两个状态设计一下,就可以得到
\(dp_{i,j}=\sum\limits_{j=1}^\sqrt{n} dp_{i-1,j} \sum\limits_{j=1}^\sqrt{n} g_{i-1,j}\)
好的,接下来,我们需要注意 \(g_{i,j}\) 怎么求,其实就等于 \(g_{i,j}= \sum\limits_{k=1}^\sqrt{n} dp_{g-1,k} \times cnt[i]\) 啦.至于 \(cnt\) 是啥,就是数论分块的块长啦 ,啥是数论分块?也就是整除分块啦.
标签：limits,分块,sum,缝隙,sqrt,Abc132,DEF,dp From： https://www.cnblogs.com/zhong114514/p/17056715.html