Loading [MathJax]/extensions/tex2jax.js

AtCoder Grand Contest 002E – Leftmost Ball 题解

主要思路

我们发现只需要保证在任何时候\(0\)的个数都大于等于颜色的数量。直接考虑一个一个塞球,不仅要考虑同质问题,还要考虑具体的颜色排列非常麻烦,不如我们一次性把所有的球都在序列上放好:设置\(dp[i][j]\)为\(i\)个\(0\)、\(j\)种颜色的局面,我们可以这样转移:

\[ dp[i][j] = dp[i – 1][j] + {n – i + (n – j + 1) \times (k – 2) – 1 \choose k – 2 } dp[i][j – 1] (n – j + 1) \]

解释一下:我们固定住该颜色的球的位置为最左能放置的点,然后乘上\(n – j + 1\)进行染色,并给剩余的\(k-2\)个球选位置。

代码

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// AGC002F.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2020, mod = 1e9 + 7;
int n, k, dp[MAX_N][MAX_N], fac[MAX_N * MAX_N], fac_inv[MAX_N * MAX_N], fac_tot;
int quick_pow(int bas, int tim)
{
int ret = 1;
while (tim)
{
if (tim & 1)
ret = 1LL * ret * bas % mod;
bas = 1LL * bas * bas % mod;
tim >>= 1;
}
return ret;
}
int comb(int upper, int lower) { return 1LL * fac[upper] * fac_inv[lower] % mod * fac_inv[upper - lower] % mod; }
int main()
{
scanf("%d%d", &n, &k), fac_tot = n * k;
if (k == 1)
puts("1"), exit(0);
for (int i = fac[0] = 1; i <= fac_tot; i++)
fac[i] = 1LL * fac[i - 1] * i % mod;
fac_inv[fac_tot] = quick_pow(fac[fac_tot], mod - 2);
for (int i = fac_tot - 1; i >= 0; i--)
fac_inv[i] = 1LL * fac_inv[i + 1] * (i + 1) % mod;
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= i; j++)
{
dp[i][j] = dp[i - 1][j];
if (j > 0)
dp[i][j] = (1LL * dp[i][j] + 1LL * comb(n - i + (n - j + 1) * (k - 1) - 1, k - 2) * dp[i][j - 1] % mod * (n - j + 1) % mod) % mod;
}
printf("%d\n", dp[n][n]);
return 0;
}
// AGC002F.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 2020, mod = 1e9 + 7; int n, k, dp[MAX_N][MAX_N], fac[MAX_N * MAX_N], fac_inv[MAX_N * MAX_N], fac_tot; int quick_pow(int bas, int tim) { int ret = 1; while (tim) { if (tim & 1) ret = 1LL * ret * bas % mod; bas = 1LL * bas * bas % mod; tim >>= 1; } return ret; } int comb(int upper, int lower) { return 1LL * fac[upper] * fac_inv[lower] % mod * fac_inv[upper - lower] % mod; } int main() { scanf("%d%d", &n, &k), fac_tot = n * k; if (k == 1) puts("1"), exit(0); for (int i = fac[0] = 1; i <= fac_tot; i++) fac[i] = 1LL * fac[i - 1] * i % mod; fac_inv[fac_tot] = quick_pow(fac[fac_tot], mod - 2); for (int i = fac_tot - 1; i >= 0; i--) fac_inv[i] = 1LL * fac_inv[i + 1] * (i + 1) % mod; dp[0][0] = 1; for (int i = 1; i <= n; i++) for (int j = 0; j <= i; j++) { dp[i][j] = dp[i - 1][j]; if (j > 0) dp[i][j] = (1LL * dp[i][j] + 1LL * comb(n - i + (n - j + 1) * (k - 1) - 1, k - 2) * dp[i][j - 1] % mod * (n - j + 1) % mod) % mod; } printf("%d\n", dp[n][n]); return 0; }
// AGC002F.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2020, mod = 1e9 + 7;

int n, k, dp[MAX_N][MAX_N], fac[MAX_N * MAX_N], fac_inv[MAX_N * MAX_N], fac_tot;

int quick_pow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

int comb(int upper, int lower) { return 1LL * fac[upper] * fac_inv[lower] % mod * fac_inv[upper - lower] % mod; }

int main()
{
    scanf("%d%d", &n, &k), fac_tot = n * k;
    if (k == 1)
        puts("1"), exit(0);
    for (int i = fac[0] = 1; i <= fac_tot; i++)
        fac[i] = 1LL * fac[i - 1] * i % mod;
    fac_inv[fac_tot] = quick_pow(fac[fac_tot], mod - 2);
    for (int i = fac_tot - 1; i >= 0; i--)
        fac_inv[i] = 1LL * fac_inv[i + 1] * (i + 1) % mod;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= i; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j > 0)
                dp[i][j] = (1LL * dp[i][j] + 1LL * comb(n - i + (n - j + 1) * (k - 1) - 1, k - 2) * dp[i][j - 1] % mod * (n - j + 1) % mod) % mod;
        }
    printf("%d\n", dp[n][n]);
    return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *