AGC002F Leftmost Ball

发表于 | 分类于

Description

有\(n\)种颜色（不包括白色）的球各\(k\)个，要求你将它们排成一列，然后将每种颜色最靠左的球染白。求最终序列的方案数。

\(1\leq n, k\leq 2000\)。

Solution

数数难，难如屑食汉（意味不明）

我们不妨将白球当做一种颜色来处理。那么我们发现只要满足最后恰有\(n\)个白球（这样其他球各有\(k - 1\)个），并且第\(i\)个白球之前出现了至多\(i - 1\)种非白颜色，那么序列就是合法的。

然后这样如果直接顺次DP的话，由于需要记所有球还有多少没用所以复杂度上天……我们考虑转换一下思路，在考虑一个颜色的时候就把该颜色所有球全安排上。那么设计状态\(f_{i, j}\)表示已经放了\(i\)个白球，然后用了\(j\)种颜色的情况（显然要求\(i\leq j\)）。那么转移的时候，我们限制不管放白球还是放非白球一定要放置在最靠左的空位（否则会记重），那么显然可以直接放一个白球，也可以放非白球，非白球的转移就是考虑放哪种球然后除了最靠左的球以外的\(k - 2\)个放哪就行了。转移方程如下： \[ f_{i, j}=f_{i - 1, j} + (n - j + 1)\binom{nk - i - (j - 1) * (k - 1) - 1}{k - 2}f_{i, j - 1} \]

Description

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
const int maxn = 2005;
using ll = long long;
const ll ha = 1000000007LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

ll fac[maxn * maxn], ifac[maxn * maxn];
void process() {
  fac[0] = 1;
  const int n = 4000005;
  for(int i = 1; i <= n; i ++) {
    fac[i] = fac[i - 1] * (ll)i % ha;
  }
  ifac[n] = inv(fac[n]);
  for(int i = n - 1; i >= 0; i --) {
    ifac[i] = ifac[i + 1] * (ll(i + 1)) % ha;
  }
}
ll C(int n, int m) {
  if(n < m) return 0;
  ll ret = fac[n] * ifac[n - m] % ha;
  ret = ret * ifac[m] % ha;
  return ret;
}

int main() {
  process();
  int n, k; scanf("%d%d", &n, &k);
  if(k == 1) {
    puts("1"); return 0;
  }
  static ll f[maxn];
  f[0] = 1;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= i; j ++) {
      ll delta = n - j + 1;
      delta = delta * C(n * k - i - (j - 1) * (k - 1) - 1, k - 2) % ha;
      delta = delta * f[j - 1] % ha;
      f[j] += delta;
      if(f[j] >= ha) f[j] -= ha;
    }
  }
  printf("%lld\n", f[n]);
  return 0;
}