放普及段的原因:
卢卡斯定理练手好题
水紫一道,顶多蓝
解题思路
该题的难点在于:脑补 \LaTeX 。
我们先分析下样例,设这四个数分别为 a_1,a_2,a_3,a_4 。
那么合并过程就可以这样表示:
a_1 \,\,\,\,\,\,\, a_2 \,\,\,\,\,\,\, a_3 \,\,\,\,\,\,\, a_4
\\a_1+a_2 \,\,\, a_2+a_3 \,\,\, a_3+a_4
\\a_1+2a_2+a_3 \, a_2+2a_3+a_4
\\a_1+3a_2+3a_3+a_4
可以发现,结果的各项系数刚好对应杨辉三角,从下往上推很容易证明。
所以只需用组合数求出各项系数。
接下来考虑贪心,由于杨辉三角中间的数最大,考虑将大数放在中间,然后就能过了。
(有无大佬证明一下,反正这个思路是能过的)
AC 代码
你说的对,但是信友队论坛不能放 AC 代码