题解 CF1228E [Another Filling the Grid]
Published:
前置知识：FMT
前言：由于本人不太喜欢推容斥式子，就借助了前人的智慧，整了个 $FMT$ 做法。
分析题目给出的限制条件：每行每列的最小值为 $1$ 。由于同时涉及到行列，就不太好用正常的方式来描述该限制条件。那么，我们就将各行分开考虑。
接下来考虑如何处理各行之间的关系，由于同一列可以选若干个 $1$ ，而每一行每一列都得有 $1$，一个比较暴力的想法是：或卷积。
对于 $n$ 很小的时候，首先我们将矩阵按行拆开成 $n$ 个长度为 $n$ 的向量，由于每个值的选择只有 $1$ 或者非 $1$ 两种选择，我们不妨设每行的选择情况为 $T$ (一个二进制数)，其中第 $k$ 位为 $1$ 表示在向量中第 $k$ 个位置填上 $1$ ，为 $0$ 则表示填上其他数。那么，我们可以写出它的集合幂级数（卷积定义为或卷积）：
\[\displaystyle f(x)=\sum_{T\neq \emptyset}(K-1)^{n-pop(T)} x^T\]其中 $pop(T)$ 表示二进制数 $T$ 中 $1$ 的个数。有了该式之后，我们将其自卷 $n$ 次后的最高项系数就是答案。具体的，将 $f(x)$ 进行 $FMT$ 后再将每一项都取 $n$ 次幂再 $IFMT$ 回来即可。即（设 $U$ 为最高次项）：
\[ans=[x^{U}] f^n(x)\]由于该做法的复杂度是 $O(n2^n)$ ，当 $n$ 略大的时候，由于该集合幂级数是指数级别增长的，这个做法似乎就裂开了。
其实不然，当我们深入分析该式子后，发现当 $pop(T)$ 相同的项其系数也相同，那么我们就不必将各个项分开考虑，只需按 $pop(T)$ 分类即可。 重新分好类之后，我们还得考虑在当前情况下如何做 $FMT$ ，根据或卷积的 $FMT$ 的定义（设 $\hat f(x)$ 为 $f(x)$ 莫比乌斯变换之后的结果）：
\[\displaystyle \hat f(x)=\sum_{T}\sum_{S\subseteq T} [x^{S}]f(x) x^{T}\]我们同理可以给幂次定义为 $pop(T)$ 的多项式类似地进行 $FMT$ ：
\[\displaystyle \hat f(x)=\sum _i \sum_{j=1}^i \binom{i}{j}(K-1)^{n-j} x^i\]你也许想对其做卷积，但是模数 $1e9+7$ 要写任意模就会把我们劝退。事实上，后式就是个二项式定理的形式，简单化一下式子就可得到：
\[\displaystyle \hat f(x)=\sum_i (K-1)^n*((\frac{K}{K-1})^i-1) x^i\]将每一项系数取 $n$ 次幂后就得考虑如何做 $IFMT$ 变回来，不过剩下的工作和以上基本相同。还是先给出 $IFMT$ 的定义：
\[\displaystyle \hat f(x)=\sum_{T}\sum_{S\subseteq T} (-1)^{|T|-S} [x^{S}]f(x) x^{T}\]由于我们只需要求最高次项系数，即 $pop(T)=n$ 的情况，以下也就只给出第 $n$ 位做 $IFMT$ 后的结果：
\[\displaystyle ans=\sum_{i=1}^n \binom{n}{i} (-1)^{n-i} [x^i]\hat f(x)\]各部分时间复杂度基本都是 $O(n)$ ，仅自乘处复杂度为 $O(n\log n)$ ，所以总时间复杂度 $O(n\log n)$ 。
#include<bits/stdc++.h>
#define re register int
#define ll long long
#define LL inline ll
#define V inline void
#define I inline int
#define FOR(i,a,b) for(re i=(a),i##i=(b);i<=i##i;++i)
#define ROF(i,a,b) for(re i=(a),i##i=(b);i>=i##i;--i)
//#define gc getchar()
#define gc (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),ft==fs))?0:*fs++
using namespace std;
char *fs,*ft,buf[1<<18];
const int N=2e5+10,mo=1e9+7;
ll inf=1e14;
LL read(){
ll p=0,w=0; char ch=gc;
while(!isdigit(ch)) w=ch=='-',ch=gc;
while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
return w?-p:p;
}
int n,K;
LL Pow(ll x,ll y){ ll as=1; for(;y;y>>=1,x=x*x%mo) if(y&1) as=as*x%mo; return as;}
V ipt(){ n=read(),K=read();}
ll f[N],g[N],h[N],fc[N],fv[N],pw[N],ans;
LL get(ll x,ll y){ return x>=y?fc[x]*fv[y]%mo*fv[x-y]%mo:0;}
V init(){
fc[0]=1,pw[0]=1;
FOR(i,1,n) fc[i]=fc[i-1]*i%mo;
fv[n]=Pow(fc[n],mo-2);
ROF(i,n,1) fv[i-1]=fv[i]*i%mo;
return ;
}
V sol(){
ll inv=Pow(K-1,mo-2)*K%mo,us=Pow(K-1,n);
pw[0]=1;
FOR(i,1,n) pw[i]=pw[i-1]*inv%mo;
FOR(i,1,n) f[i]=us*(pw[i]-1+mo)%mo;
FOR(i,1,n) f[i]=Pow(f[i],n);
FOR(i,1,n) ans=(ans+((n-i)&1?mo-1:1)*get(n,i)%mo*f[i])%mo;
cout<<ans;
return ;
}
int main(){
ipt();
init();
if(K!=1) sol();
else cout<<1;
return 0;
}