2019牛客暑期多校训练营(第七场)I Chessboard —— 组合,n个球放入m个盒子的情况数
题意:
你可以选择k*k的矩形,每个格子中填的数要大于等于m,并且要保证(所有不同行不同列的数之和)的所有情况相同。
题解:
不会,,按照它的题解做吧,我这里就翻译一下将一些细节说的明白一点
首先,这里是设一个函数,那么为什么
因为每个格子至少要放m个,那么不同行不同列的个数是k,所以变成了T-k*m
那么对于要满足“不同行不同列的数之和”全相等这个条件,对于任意一行中,每个数都必须相等,列也同样,这样的话之后选到了不同行的时候就能够保证数是相等的。
那么对于为什么是
其实我也不太懂,这里有一个博客它讲了所有的情况:
This way
那么这时候会有重复的情况,什么重复的情况呢,也就是将所有行-1,所有列+1的时候,他们是相同的,比如说:
和
这两种情况是一样的,那么对于所有行都加了至少1的时候,我们必须要剪掉一种情况
就是说一半允许空箱,一半不允许空箱的情况,那么就是k个格子放好了球,k个没放的空箱问题,那么就是这个式子了