2023-08-07 16:29:49
题意
有一个 \(n\times m\)的矩阵，求使得每个 \(n\times n\)的矩阵中都有正好 \(k\)个点的方案数，方案数对 \(1e9+7\) 取模。 \(1\le n\le100,n\le m\le10^{18},0\le k\le n^2\)。
思路
通过观察样例并且自己手玩了一些数据后，我们发现，假设第 \(i\) 列放了 \(k\) 个数，那么如果 \(i+rn\) 列想做到前 \(n\) 列的点数和与 \(i\) 列前 \(n\) 列点数和相同，那么也得放 \(k\) 个。
所以我们只需要处理前 \(n\) 的情况就能推广到 \(m\) 列的情况了。只需要把这些相同的方案相乘即可,具体就是算取的时候带个指数吧。
转移很好想，令 \(f_{i,k}\) 表示前 \(i\) 列有 \(k\) 个点的方案数，\(x\) 表示 \(i\) 列放了 \(x\) 个点。那么有转移：
\[f_{i,k}=\sum\limits_{x=0}^{min(k,n)}f_{i-1,k-x}\times \binom{n}{x}^{m/n+(m \mod n\le i)} \]\(O(n^2\log)\)预处理 \(\binom{n}{x}^{m/n+(m \mod n\le i)}\)，然后 \(O(n^2K)\) 转移，空间复杂度 \(O(nK)\)，也可以滚到 \(O(K)\)。
\(Code\)
ll n,m,K,fac[105],ifac[105],f[105][10005],cnt[105][105];
ll qpow(ll x,ll w){
ll res=1;
for(;w;w>>=1,x=x*x%mod)if(w&1)res=res*x%mod;
return res;
}
ll C(ll x,ll y){
return (fac[x]%mod*ifac[y]%mod)%mod*ifac[x-y]%mod;
}
int main(){
cin>>n>>m>>K;
fac[0]=1;
for(ll i=1;i<=n;i++){
fac[i]=fac[i-1]*i%mod;
cnt[n+1][i]=(m/n+(m%n>=i))%(mod-1);
}
ifac[n]=qpow(fac[n],mod-2);
for(ll i=n-1;~i;--i){
ifac[i]=ifac[i+1]*(i+1)%mod;
}
for(ll i=0;i<=n;i++)
for(ll j=1;j<=n;j++)
cnt[i][j]=qpow(C(n,i),cnt[n+1][j]);
f[0][0]=1;
for(ll i=1;i<=n;i++)
for(ll k=0;k<=K;k++)
for(ll x=0;x<=min(n,k);x++){
f[i][k]=(f[i][k]+f[i-1][k-x]*cnt[x][i]%mod)%mod;
}
cout<<f[n][K];
}