不妨钦定组之间的顺序是最小值越小的组越靠前,这样可以给每个组按顺序编号。
设 \(f_{i,j}\) 为考虑了模 \(m\) 后 \(< i\) 的数,目前有 \(j\) 个非空组的方案数。
转移就是枚举模 \(m = i - 1\) 的数新开了 \(k\) 个组,设 \(\le n\) 的数中模 \(m = i - 1\) 的数有 \(t\) 个,有转移:
\[f_{i,j} \gets f_{i-1,j-k} \times \binom{t}{k} \times \binom{j-k}{t-k} \times (t-k)!
\]
意思就是从这 \(t\) 个数中选出 \(k\) 个数分到编号 \(j - k + 1 \sim j\) 的组,在已有的 \(j-k\) 个组中选 \(t-k\) 个组给剩下不用新开一组的数放进去,顺序任意。
答案为 \(f_{m,i}\)。
时间复杂度 \(O(n^2)\)。
code
// Problem: G - Groups
// Contest: AtCoder - AtCoder Beginner Contest 217
// URL: https://atcoder.jp/contests/abc217/tasks/abc217_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 5050;
const int N = 5000;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, m, a[maxn], fac[maxn], ifac[maxn], f[maxn][maxn];
void init() {
fac[0] = 1;
for (int i = 1; i <= N; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[N] = qpow(fac[N], mod - 2);
for (int i = N - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
}
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%lld%lld", &n, &m);
f[0][0] = 1;
for (int i = 1; i <= m; ++i) {
int t = n / m + (i <= n % m);
for (int j = 0; j <= n; ++j) {
for (int k = 0; k <= min(j, t); ++k) {
f[i][j] = (f[i][j] + f[i - 1][j - k] * C(t, k) % mod * C(j - k, t - k) % mod * fac[t - k] % mod) % mod;
}
}
}
for (int i = 1; i <= n; ++i) {
printf("%lld\n", f[m][i]);
}
}
int main() {
init();
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest Groups 217beginner atcoder contest groups beginner atcoder contest 217 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334