题意:
在 n×m 网格中安排点,要求任意 n×n 矩阵中恰有 k 个点。求方案数。
\(n\le 100,n\le m \le 1e18, 0\le k\le n^2\)
思路:
观察发现第 i 列和第 i+n 列的点数须相等。下面的列 i 均指所有模 n 余 i 的列。
\(f[i][j]\) 表示在第 \(1 \sim i\) 列中选 \(j\) 个的方案数,\(j\in [0,k]\)。 枚举第 \(i\) 列放 \(t\) 个,\(t\in [0,min\{n,k\}]\)
\(f[i][j]=\sum \limits_{t=0}^{min\{n,j\}} f[i-1][j-t]\times (C_n^t)^{cnt_i}\)
答案是 \(f[n][k]\)
const int N = 110;
const ll MOD = 1e9 + 7;
ll n, m, k, C[N][N], po[N][N], f[N][N*N];
ll qmi(ll a, ll b, ll p = MOD)
{
ll res = 1;
while(b) {
if(b & 1) res = res * a % p;
a = a * a % p, b >>= 1;
}
return res;
}
ll cnt(ll i)
{
return i <= m%n ? m/n + 1 : m/n;
}
signed main()
{
cin >> n >> m >> k;
for(int i = 0; i <= n; i++) //预处理组合数
{
C[i][0] = 1;
for(int j = 1; j <= i; j++)
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
for(int i = 0; i <= n; i++) //预处理幂
for(int j = 1; j <= n; j++)
po[i][j] = qmi(C[n][i], cnt(j));
f[0][0] = 1;
for(ll i = 1; i <= n; i++)
for(ll j = 0; j <= k; j++)
for(ll t = 0; t <= min(n, j); t++)
(f[i][j] += f[i-1][j-t] * po[t][i] % MOD) %= MOD;
cout << f[n][k];
}