AtCoder Beginner Contest 251 Solution

更好的阅读体验戳此进入

题面链接

题面 Luogu 链接

老样子abc太水了就跳了

[ABC251D] At Most 3 (Contestant ver.)

题面

给你整数 W(1W106)。 你必须构造一个数组 a,包含最多 300 个元素,使得小于等于 W 的所有正整数都可以被 a 数组的元素相加表示出来。

Solution

显然按照十进制拆分成三组即可,即 [1,99],[100,9900],[10000,990000] 即可,共 99×3=297 个。

Code

[ABC251E] Takahashi and Animals

题面

n 只动物围成一圈,你可以花费 a[i] 喂食动物 ii+1。特别地,你可以花费 a[n] 喂食动物 n1

输出喂食所有动物需要的最小花费。

Solution

DP 显然,令 dp(i,0/1) 表示考虑前 i 个元素且最后一个元素不喂 / 喂的最小花费。转移显然,注意要考虑一下 N1 之间,具体选择哪个即可。

Code

[ABC251F] Two Spanning Trees

题面

给定无向连通简单图,求其两个以 1 为根的生成树 T1,T2,满足:

Solution

前者对图 DFS,后者对图 BFS,证明显然。

Code

G 是计算几何,暂时跳了,以后有机会再回来做

[ABC251Ex] Fill Triangle

题面

存在序列 an,将其压缩后给定。具体地,给定序列 P 以如下形式:((a1,c1),(a2,c2),,(am,cm)),表示序列 a 中有 c1a1c2a2,以此类推,且按序拼接。令序列 an 为三角金字塔 B 的第 n 层,即 B(n,i)=ai。特别地,该三角金字塔的递推式为 B(i,j)=(B(i+1,j)+B(i+1,j+1))mod7。给定 k,求该三角金字塔第 k 层的序列。

Solution

首先可以尝试随意给定一个序列 an 并打表,或手推一下,假设 n=5,有:

a1+4a2+6a3+4a4+a5    
a1+3a2+3a3+a4a2+3a3+3a4+a5   
a1+2a2+a3a2+2a3+a4a3+2a4+a5  
a1+a2a2+a3a3+a4a4+a5 
a1a2a3a4a5

不难发现这玩意每一项实际上就是二项式系数,或者说杨辉三角。并且还能发现,对于每一行的元素,它们的系数均相同,不同的只是将下标整体向右平移了一位。

此时我们便可以根据这个性质,求出对于第 k 层,第 x 列的元素,有:

B(k,x)=i=0nk(nki)ax+imod7

显然我们想要算出 k 层的所有元素,但是直接套这个式子暴力算是肯定过不了的。考虑优化。

显然序列 a 是由一段一段的相同元素构成的,而我们的查询就是在 a 里的查询一个区间然后按序将组合数乘上去。当我们从 B(k,x)B(k,x+1) 的时候,通过我们之前的结论可知需要将下标向右平移一位,而所有组合数的值不变,大概的过程如图:

Oops! The image is blocked! Please visit my own website to observe the image! 图片被墙了,请通过文章头的跳转链接访问!

观察发现,这个东西平移之后,对于大多数的 (nki)×ax+i 变成 (nki)×ax+i+1,都存在 ax+i=ax+i+1,而对于这些的贡献是完全不变的。不难想到这个变化操作的复杂度最多是 O(m) 的。所以当我们确定了 B(k,1) 之后,后面的 B(k,2)B(k,k) 就都可以每次 O(m) 求解,故这步的复杂度优化为 O(mk)

具体地当我们移动询问区间的时候,遍历所有段,如果某一段的右端点在当前区间内,那么显然指向这一段的组合数会移动到下一段中,所以需要减掉前面的加上现在的。注意移动这步实际上是 O(mklogn) 的,而且这只 log 不小,所以会 TLE,则我们考虑预处理 Lucas。显然直接预处理 109 范围肯定不行,于是这里有个高妙的思路,我们本身的模数为 7,那么我们可以先让值对 7k 取模,然后再对 7 取模,这个显然是等价的。而如果我们搞一个 105 左右的 7k 的话,那么一步 Lucas 之后需要求的组合数就都在 105 以内了,所以这个时候我们只需要预处理 105 以内的组合数,那么对于每次求 Lucas 直接拆一次但是不递归,直接查值乘起来取模即可,这样复杂度就是 O(1) 了,或者说 O(2),于是复杂度会变成 O(mk)。同时不难发现,存在 $ $

于是现在的问题就仅剩如何求 B(k,1),也就是求:

i=0nk(nki)ai+1mod7

首先还是考虑之前的思路,一定会有很多段的相同的 a,假设我们存在一段 [l,r] 满足 i[l,r),ai=ai+1,那么显然此处的值即为:

i=l1r1(nki)ai+1mod7

所以这个东西显然需要快速处理一段组合数,可以考虑做一个组合数的前缀和,这样即可 O(1) 查询一段组合数的求和,然后乘上 al 即可,这样每次的复杂度也就是 O(m) 了。当然我们肯定不能对于 nk 以内的每个数求前缀和,所以可以对 m 段相同的分别求出对应的前缀和,然后查询即可。求的时候前面段的直接求和,最后剩下的不足一段的单独计算即可。

于是现在问题再次转化为如何快速求这种形式的组合数前缀和,可以参考该题:LG-P4345 [SHOI2015]超能粒子炮·改

具体地,对于求 F(n,k)=i=0k(ni)modp,且 p 为质数,可以尝试通过 Lucas 进行处理(后面的式子最终都需要取模,这里省略):

i=0k(ni)modp=i=0k(npip)×(nmodpimodp)

然后发现对于前面的 ip,这个就是个数论分块,也可以按照这个思想,将原式化为:

(np0)i=0p1(nmodpimodp)+(np1)i=0p1(nmodpimodp)++(npkp1)i=0p1(nmodpimodp)+(npkp)i=0kmodp(nmodpimodp)

然后继续转化:

i=0p1(nmodpimodp)×i=0kp1(npi)+(npkp)i=0kmodp(nmodpimodp)

此时对比我们之前设的 F(n,k)=i=0k(ni)modp,所以原式可以再次化为:

F(nmodp,p1)×F(np,kp1)+(npkp)×F(nmodp,kmodp)

然后我们只要随便与处理一下 p 以内的 F,这样 F(nmodp,p1)F(nmodp,kmodp) 即可 O(1) 查表,然后组合数直接用 Lucas 暴力算一下即可,对于 F(np,kp1) 递归下去即可。

考虑这个东西的复杂度,用主定理推导一下即可:

T(n)=T(np)+f(n)

O(n) 处理一下组合数,则 f(n) 的复杂度只有 Lucas 的一只 log,所以最终这里单次求解的复杂度为 O(log2n),然后我们要处理 m 个,则最终这步的复杂度为 O(mlog2n)。最终复杂度为 O(mk+mlog2n+klogn),显然能过。

至此我们就终于完成了这道题。

Code

UPD

update-2022_12_02 初稿