E. Height All the Same
E. Height All the Same
标签 组合数学 二项式定理 简明题意 给定n*m的矩阵,每一个a[i][j]代表(i,j)的高度。你可以执行两种操作： 1.给任意一个a[i][j]加上2. 2.给两个相邻的格子都加1. 现在给出n，m，l，r，问你n*m的矩阵，每个格点的初始值是[l,r]中的任意一个，问有多少种初始值，可以使得经过上面的2种操作，所有格点的值相同。 思路 假设每个格点的高度已知，那么如何判断是否能通过上面的操作使得全部相等呢？实际上可以从奇偶性的角度考虑。 如果所有格点都是奇数或者都是偶数，那么很显然通过操作1即可。接下来考虑既有奇数格点又有偶数格点的情况。 我们想想操作2的作用。显然是将奇偶性反转。假如有4个格点是奇数，那么可以通过操作2将这4个格点全部变成偶数。概括一下，也就是同奇偶性的数的偶数，那么可以先通过操作2使得所有数的奇偶性相同，再通过操作1使得所有数相等。 综上，所有数奇偶性相同可行，奇数有偶数种可行，偶数有偶数种可行。唯一不可行的是：奇数和偶数都是奇数种。 记下来思考如何计算答案。 nm是奇数。那么奇数和偶数总有一种的个数是偶数。所以怎么填都可行。答案就是：每个点可以填L-R中的任意一个，也就是每个格点可以填(R-L)种数，一共有nm个格点，答案就是(R−L)n∗m(R-L)^{n*m}(R−L)n∗m 2.n*m是偶数。 那么我们先从n*m个格子中选出偶数个格子，Cn∗miC_{n*m}^{i}Cn∗mi。再把这些格子填成偶数，xix^{i}xi，剩下的格子填奇数：yn∗m−iy^{n*m-i}yn∗m−i，所以最后答案就是：∑i=0且i为偶数n∗mCn∗mixiyn∗m−i\sum_{i=0且i为偶数}^{n*m}C_{n*m}^{i}x^{i}y^{n*m-i}i=0且i为偶数∑n∗mCn∗mixiyn∗m−i 回忆二项式定理：
(x+y)n=∑i=0nCnixiyn−i(x+y)^n=\sum_{i=0}^n C_{n}^{i}x^iy^{n-i}(x+y)n=i=0∑nCnixiyn−i 因此上式，我们实际求的是，二项式展开后的偶数项。我们可以构造出一个
(x−y)n=∑i=0nCnixi(−y)n−i(x-y)^n=\sum_{i=0}^n C_{n}^{i}x^i(-y)^{n-i}(x−y)n=i=0∑nCnixi(−y)n−i 这个式子中，i为奇数，n-i也是奇数，那么n为奇数时，这一项就是负数。所以{(x+y)n+(x−y)n}/2\{(x+y)^n+(x-y)^n\} / 2{(x+y)n+(x−y)n}/2刚好把奇数项抵消了，求出来就是二项式偶数项的和。 所以n*m是偶数时，答案就是{(x+y)n+m+(x−y)n+m}/2\{(x+y)^{n+m}+(x-y)^{n+m} \}/ 2{(x+y)n+m+(x−y)n+m}/2 注意事项 无 总结 Cnixiyn−iC_{n}^{i}x_iy^{n-i}Cnixiyn−i要立马想到二项式定理。 求二项式展开后的奇/偶数项，要想到构造抵消。 模意义下不要提前给指数取模了。 AC代码
#pragma GCC optimize(2)
#include
#include
#include
#include
#include
#include
作者：dan__zh
