[latexpage]
ACM重在做题啊，通过做题发现自己的知识缺陷，比如今天遇到的这道题（CF1228E ):
Another Filling the Grid
You have n×nn×n square grid and an integer kk. Put an integer in each cell while satisfying the conditions below.
All numbers in the grid should be between 11 and kk inclusive.
Minimum number of the ii-th row is 11 (1≤i≤n1≤i≤n).
Minimum number of the jj-th column is 11 (1≤j≤n1≤j≤n).
Find the number of ways to put integers in the grid. Since the answer can be very large, find the answer modulo (109+7)(109+7).
Input
The only line contains two integers nn and kk (1≤n≤2501≤n≤250, 1≤k≤1091≤k≤109).
Output
Print the answer modulo (109+7)(109+7).
知识准备
容斥原理
来源：
其实就是集合论、概率论里的P(A+B+C)=P(A)+P(B)+P(C)-P(AB)-P(BC)-P(AC)+P(ABC)
这道题里的话最后列出如下式子：
$\sum_{i=0}^n \sum_{j=0}^n (-1)^{i+j} C_n^i C_n^j {(k-1)}^{ni+nj-ij} k^{n^2-ni-nj+ij}$
解释：
1、先忽视最小值限制考虑所有的填法，在减去某一行没有1和某列没有1的情况，
2、但是 某行没有1 的情况里在 第i行没有1时 减去了 第i行没有1 且 第j行没有1 的情况，而在第j行里也减去了这种情况，于是所有某两行没有1的情况都被多减了一次，某列没有1也有同样的情况，
3、而且某行没有1的时候减去了某行某列没有1的情况而在某列没有1的时侯也减去了，于是某行某列没有1的情况也被重复减去了，
4、所以要把某两行没有1、某两列没有1，某行某列没有1的情况给加回来
5、1中重复减去了三次某三行没有1的情况，但4中又加上了三次某三行没有1的情况，于是又要重新减去一次某三行没有1的情况，某三列，某行某两列，某两行两列的情况类似
6、以此类推得出上文公式
改进:
某些数学大佬还用二项式定理对上文公式进行了简化，如下：
$\sum_{i=0}^{n} (-1)^i \cdot C_n^i \cdot (k^{n-i} \cdot (k-1)^{i} – (k-1)^{n})^n$
快速幂
原本算a8，就是乘8次a，算法效率为o(n)，但如果我们把a8拆成((a2)2)2，效率就变为了o(log2n)；原本算ab，就是乘b次a，算法效率为o(n)，但如果我们把ab拆成a2b1a2b2…a2bn，效率就变为了后者可以利用前者的结果继续累乘。
实现如下：
int quick_pow(int a,int b)
{
int ans=1,base=a;
for(;b;b>>=1,base*=base)
if(b & 1)ans=ans*base;
return ans;
}
逆元
大佬写的比我好，韩式看大佬的吧https://blog.csdn.net/qq_35416331/article/details/81059747
这道题用快速幂模和阶乘递推就好了，10^9+7是一个质数，快速幂模就是快速幂的每一步都求个模。
实现如下：
mod = 1000000007
long long quick_pow(long long a,long long b){
long long ans=1,base=a%mod;
for(;b;b>>=1,base*=base%mod)
if(b & 1)ans=ans*base%mod;
return ans;
}
long long inv(long long a){
return quick_pow(a,mod-2);
}
long long inv2(long long a){
return inv(a+1)*(a+1)%mod;
}
参考实现
#include<bits/stdc++.h>
#define max_size 251
#define mod 1000000007
long long fact[max_size],invfact[max_size],C[max_size];//阶乘、逆元、组合数打表
long long quick_pow(long long a,long long b)//快速幂模
{
long long ans=1,base=a;
for(;b;b>>=1,base=base*base%mod)
if(b & 1)ans=ans*base%mod;
return ans;
}
long long inv(long long a)//逆元
{
return quick_pow(a,mod-2);
}
long long inv2(long long a)//阶乘逆元
{
return invfact[a+1]*(a+1)%mod;
}
void init(long long n){//打足够用的表
fact[0]=1;
long long i;
for(i=1;i<=n;i++)
fact[i]=fact[i-1]*i%mod;
invfact[n]=inv(fact[n]);
for(i=n-1;i>=0;i--)invfact[i]=inv2(i);//数据范围搞清楚啊
for(i=0;i<n/2+1;i++) C[i]=fact[n]*invfact[n-i]%mod*invfact[i]%mod;
for(;i<=n;i++) C[i]=C[n-i];
}
int main(){
long long n,k;
scanf("%lld%lld",&n,&k);
init(n);
long long res=0;
for(long long i=0;i<=n;i++){
for(long long j=0;j<n;j++){
long long u=n*i+n*j-i*j;
res+=quick_pow(-1,i+j)*C[i]%mod*C[j]%mod*quick_pow(k-1,u)%mod*quick_pow(k,n*n-u)%mod;//随时mod一下
res=(res+mod)%mod; //为啥不加这句就错了啊，也没输出负数啊！！！！！
}
}
printf("%lld\n",res);
return 0;
}
