CF1228E solution

· · 题解

这里提供一个便于理解的容斥写法：

首先，一行的所有数合法的情况数为 k^n-(k-1)^n （即所有情况减去最小值大于 1 的情况）。

然后，我们枚举至少 i 列不合法（严格上来说是容斥的辅助数组），相当于每行中钦定了 i 个数最小值大于 1 ，则每行的合法方案数为 k^{n-i}(k-1)^i-(k-1)^n ，乘上组合数并把每一行乘起来得到 \tbinom{n}{i}(k^{n-i}(k-1)^i-(k-1)^n)^n 。

最后容斥，答案为 \displaystyle\sum_{i=0}^n(-1)^i\tbinom{n}{i}(k^{n-i}(k-1)^i-(k-1)^n)^n ，时间复杂度 O(n\log n) 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,mod=1e9+7;
ll n,k,jc[N],jv[N],mi1[N],mi2[N],ans;
ll ksm(ll di,ll mi) {ll res=1; for(di%=mod;mi;mi>>=1,di=di*di%mod) if(mi&1) res=res*di%mod; return res;}
ll c(ll a,ll b) {return jc[a]*jv[b]%mod*jv[a-b]%mod;}
int main()
{
    int i,j;
    for(cin>>n>>k,jc[0]=mi1[0]=mi2[0]=i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod,mi1[i]=mi1[i-1]*k%mod,mi2[i]=mi2[i-1]*(k-1)%mod;
    for(jv[n]=ksm(jc[n],mod-2),i=n-1;~i;i--) jv[i]=jv[i+1]*(i+1)%mod;
    for(i=0;i<=n;i++) ans=(ans+(i&1? mod-1:1)*(c(n,i)*ksm(mi1[n-i]*mi2[i]+mod-mi2[n],n)%mod))%mod;
    cout<<ans;
    return 0;
}