Placing Jinas

发布时间 2023-11-01 08:46:39作者: Zlc晨鑫

传送门

对于这种网格图的操作,因为是加法操作,所以可以有结合律和交换律,也就是说操作顺序是无关紧要的。

所以从上到下,从左到右考虑所有操作。

对于第一个格子的\(1\),它一定要被减去1次,而且只能被减去1次,因为只有在它格子上操作才能影响到它,它不可能被其他格子的操作加上1。

此时第一个格子的操作考虑完了,考虑第二个格子,同样,它有且仅有一次操作,因为只有第一个格子能影响到它,但是第一个格子已经考虑完了。

……

然后会发现是下面的矩阵求和,每一行有\(a_i\)项。

\[\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 3 & 6 & 10 & 15 & 21 \\ 1 & 4 & 10 & 20 & 35 & 56 \\ \end{matrix} \]

会发现有递推式\(f_{i,j}=f_{i-1,j}+f_{i,j-1}\)

这就想到组合数\(\binom{m}{n}=\binom{m-1}{n-1}+\binom{m}{n-1}\)

让后你就发现这就是杨辉三角。

具体来说,矩阵是

\[\begin{matrix} \binom{0}{0} & \binom{1}{1} & \binom{2}{2} & \binom{3}{3} \\ \binom{0}{1} & \binom{1}{2} & \binom{2}{3} \\ \binom{0}{2} & \binom{1}{3} \\ \binom{0}{3} \\ \end{matrix} \]

\(0\le x \le n+1,0\le y\le a_x-1,f_{x,y}=\binom{y}{x+y}\)

这个时候化简式子一般都是把某些常数换成合适的形式,然后用递推式化简。

因为递推式的下面的数一定要相同,所以这样化简:

\(\binom{0}{x}+\binom{1}{x+1}+\binom{2}{x+2}+...=\binom{0}{x+1}+\binom{1}{x+1}+...=\binom{1}{x+2}+...=\binom{a_x-1}{x+a_x}\)

然后就做完了。