我们首先可以观察到这道题的 \(m\) 很大，所以要考虑这么多列里面是否存在一个性质，让我们求出前 \(n\) 列之后快速求出后 \(m\) 列的答案。观察一下可以发现第 \(i,j\) 两列的答案等价时满足 \(i \equiv j \pmod n\)。这样的话我们只需要求出前 \(n\) 列的答案即可。记 \(s_i\) 为这 \(m\) 列中答案与第 \(i\) 列等价的列数，\(f_{i,j}\) 表示前 \(i\) 列涂色 \(j\) 个格子的方案数，此时显然有一个转移：
\[f_{i,j}=\sum \limits_{p=0}^{\min{(j,n)}}{f_{i-1,j-p} \binom{n}{p}^{s_i}}
\]
我们先预处理 \(\binom {n}{p}s_i\) 再转移，即可实现在 \(O(n^2k)\) 的时间内解决这个问题。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int n,m,k;
int C[110][110];
int quickpow(int x,int p){
int ans=1;
while(p){
if(p&1) ans=ans*x%mod;
x=x*x%mod;
p>>=1;
}
return ans;
}
void init(){
for(int i=1;i<=100;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++){
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
}
}
int pre[110][110];
int f[110][10010];
signed main(){
init();
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
int key;
if(m%n==0) key=m/n;
else{
if(i<=m%n) key=m/n+1;
else key=m/n;
}
pre[i][j]=quickpow(C[n][j],key);
}
}
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=min(i*n,k);j++){
for(int p=0;p<=min(n,j);p++){
f[i][j]+=f[i-1][j-p]*pre[i][p];
f[i][j]%=mod;
}
}
}
cout<<f[n][k]%mod<<endl;
return 0;
}