Another Filling the Grid
二维的二项式反演。
考虑钦定法。
钦定合法的行和列似乎有些困难，所以我们尝试钦定不合法的行和列。
令 $f(a,b)$ 表示钦定 $a$ 行不合法，$b$ 列不合法，于是有：
$$f(a,b)=\binom{n}{a}\binom{n}{b}(k-1) ^ {na}(k-1) ^ {(n-a)b} k ^ { ( n - a ) ( n - b ) }$$
组合意义是，先选中 $a$ 行和 $b$ 列，然后 $a$ 行都不合法，$b$ 列都不合法（但是去掉钦定的 $a$ 行），然后其余摆烂。
然后我们考虑令 $g(a,b)$ 表示恰好有 $a$ 行不合法，$b$ 列不合法。于是我们有：
$$f(a,b) = \sum _ {i=a} ^ {n}\sum _ {j=b} ^ {n} \binom{i}{a} \binom{j}{b} g(i,j)$$
二项式反演，于是有：
$$g(a,b) = \sum _ {i=a} ^ {n} \sum _ {j=b} ^ {n} (-1) ^ {i-a} \binom{i}{a} (-1) ^ {j-b} \binom{j}{b} f(i,j)$$
我们要求的答案即：
$$g(0,0) = \sum _ {i=0} ^ {n} \sum _ {j=0} ^ {n} (-1)^{i} (-1)^{j} f(i,j)$$
复杂度是 $O(n^2\log n)$ 的。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
const ll N=1e3,mo=1e9+7;
inline ll Pow(ll b,ll p) {
ll r=1;while(p) {if(p&1) r=r*b%mo;b=b*b%mo;p>>=1;}return r;
}
ll n,k,ans;
ll f[N+5][N+5],fac[N+5],invfac[N+5];
inline void Init() {
fac[0]=1;for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%mo;
invfac[0]=1;invfac[n]=Pow(fac[n],mo-2);
for(ll i=n-1;i>=1;i--) invfac[i]=invfac[i+1]*(i+1)%mo;
}
inline ll C(ll n,ll m) {return (fac[n]*invfac[m]%mo)*invfac[n-m]%mo;}
int main() {
n=read();k=read();Init();
for(ll i=0;i<=n;i++) {
for(ll j=0;j<=n;j++) {
f[i][j]=C(n,i)*C(n,j)%mo;
f[i][j]=f[i][j]*Pow(k-1,n*i)%mo;
f[i][j]=f[i][j]*Pow(k-1,(n-i)*j)%mo;
f[i][j]=f[i][j]*Pow(k,(n-i)*(n-j))%mo;
}
}
for(ll i=0;i<=n;i++) {
for(ll j=0;j<=n;j++) {
if((i+j)&1) {ans=(ans-f[i][j]+mo)%mo;}
else {ans=(ans+f[i][j])%mo;}
}
}
write(ans);
return 0;
}
|