[AGC002F] Leftmost Ball 题解

题目链接：[AGC002F] Leftmost Ball

题意：

给你 $n$ 种颜色的球，每种颜色的球有 $k$ 个，把这 $n\times k$ 个球排成一排，

把每一种颜色的最左边出现的球涂成白色(初始球不包含白色)，求有多少种不同的颜色序列。

答案对 $10^9+7$ 取模。

数据范围：

$1\leq n, k\leq 2000$。

可以看作 $n$ 个白球和 $n$ 种颜色的各 $k-1$ 个球。特判 $k=1$ 。

设 $f(i,j)$ 为放了 $i$ 个白球和 $j$ 种其他颜色的球的合法方案数。

这里规定 $j \le i$ ，称每个白球右侧到下一个白球前的位置为空位。考虑转移。

• 在左侧第一个空位放一个白球，从 $f(i-1,j)$ 处转移；

• 在左侧第一个空位放至少一个其他颜色的球，然后放完该颜色的球，

  即从 $f(i,j-1)$ 处转移。考虑转移系数。首先从剩下 $n-j+1$ 种球里选一种放，

  然后在剩下的 $nk-i-(j-1)(k-1)-1$ 个空位里放 $k-2$ 个（第一个空位至少放一个）

那么转移方程就是

$$f(i,j) = f(i-1,j) + f(i, j - 1) (n - j + 1) \binom{nk-i-(j-1)(k-1)-1}{k-2}$$

时间复杂度 $\mathcal{O}(nk)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
const int mod = 1e9 + 7;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
template<typename T> void add(T &x, T y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e3 + 15))
#define N2 ((int)(4e6 + 15))

ll fac[N2], ifac[N2], dp[N][N];
ll C(int n, int m)
{
    if(n < m || m < 0) return 0;
    return fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}
ll qpow(ll a, int b)
{
    ll r = 1;
    for(a %= mod; b; b >>= 1, a = a * a % mod)
        if(b & 1) r = r * a % mod;
    return r;
}
void init(int n)
{
    fac[0] = 1;
    rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
    ifac[n] = qpow(fac[n], mod - 2);
    Rep(i, n - 1, 0) ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, k; cin >> n >> k; init(N2 - 5);
    if(k == 1) { return cout << "1\n", 0; }
    dp[0][0] = 1;
    rep(i, 1, n) rep(j, 0, i)
    {
        dp[i][j] = dp[i - 1][j];
        if(j)
        {
            const ll _1 = dp[i][j - 1] * (n - j + 1) % mod;
            const ll _2 = C(n - i + (n - j + 1) * (k - 1) - 1, k - 2);
            add(dp[i][j], _1 * _2 % mod);
        }
    }
    cout << dp[n][n] << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/pbm4dc6q

[2] https://www.luogu.com.cn/article/rpbu0cuz