[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