• 周五. 3月 29th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

快乐的一天从AC开始 | 20210806 | CF1549E

admin

11月 28, 2021

题目链接

每日吐槽

今天无心上班,摸鱼,之后估计又要忙起来了

早下班欧耶

心路历程

看题解才做出来的

思路

解法1

看完之后很容易能写出(ans = sum_{i = 1}^{n} C_{3i}^{x}),对于每一个(x)都求出答案,之后回答询问就可以(O(1))了。

然后可以用动态规划加速求解,记(dp_{x, y} = sum_{i = 0}^{n – 1} C_{3_i + y}^{x}, 0 le y le 2),那么有(ans = dp_{x, 0} + C_{3n}^{x}),且(dp_{x, 0} = dp_{x, 1} = dp_{x, 2} = n)

然后就可以推出:

  • (dp_{x + 1, 1} = dp_{x, 0} + dp_{x + 1, 0})
  • (dp_{x + 1, 2} = dp_{x, 1} + dp_{x + 1, 1})

还有(dp_{x + 1, 0})不知道咋求,多了3个未知数,但只有两个方程,还差一个方程才能解。

(dp_{x, 0})(dp_{x, 1})(dp_{x, 2})加起来有(dp_{x, 0} + dp_{x, 1} + dp_{x, 2} = C_{3n}^{x + 1}),把左边都拆成和式就是(sum_{i = 1}^{3n – 1} C_{i}^{x}),而右边相当于将选出来的最大的数作为(i),然后再选。这一步我只是感性理解,其实就是Hockey Stick Identity。

然后现在3个未知数,3个方程,解起来应该没啥问题吧

解法2

用生成函数也能做,不过懒得写了

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注