以前做过,现在来整理思路
因为白球是一种特殊的球只会存在于一种颜色所有球的最前面,所以我们考虑把白球和其他球分开来
\(dp[i][j]\)表示我们已经放置了\(i\)个白球和\(j\)种颜色的球的方案数,显然必须满足\(j \leq i\)
转移有两种
1.上一次放了一个白球
2.上一次放了一种颜色的球,即放了\(k-1\)个相同颜色的球
放白球必须尽量靠前,为了避免重复,我们把白球放在第一个空位上。
如果不是在第一个空位上,而是在任意空位上,则有可能导致某个白球不是某种颜色球的第一个,
而且在DP时不同时候放的白球可能会导致最终结果重复。
放白球的贡献为\(dp[i-1][j]\)
放有颜色的球,首先要从\(n - j + 1\)种颜色中选一个
然后我们剩下了\(n * k - i - (j - 1)*(k - 1)\)个空位,我们需要从中选\(k - 1\)个空位放我们的球,
但是贡献并不是\(C_{n * k - i - (j - 1)*(k - 1)}^{k-1}\),而是\(C_{n * k - i - (j - 1)*(k - 1)-1}^{k-2}\)
原因还是重复,如果我们不取出一个球,把第一个空位占掉,那么对于任意两次放有颜色球的操作,其结果可能是一样的,但是计算会重复
假设一下,我有四个空位,每次放两个有颜色的球,一共放两次。
第一次,选红色, 放2,3位; 第二次,选蓝色,放1,4位
和
第一次,选蓝色, 放1,4位; 第二次,选红色,放2,3位
是一样的,这就是不把第一个空位占掉导致的重复
贡献为\((n - j + 1) * C_{n * k - i - (j - 1)*(k - 1)-1}^{k-2}\)
注意k=1!!!
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int n,k;
int dp[2050][2050];
int fac[4000050],inv[4000050];
int ksm(int x,int y){
int z = 1;
while(y){
if(y & 1) z = z * x % mod;
y >>= 1;
x = x * x % mod;
}
return z;
}
int C(int n,int m){
if(n < m || m < 0) return 0;
if(n == m || m == 0) return 1;
return (fac[n] * inv[m] % mod) * inv[n - m] % mod;
}
signed main(){
scanf("%lld%lld",&n,&k);
fac[0] = 1;
for(int i = 1; i <= 4000000; ++ i) fac[i] = fac[i - 1] * i % mod;
inv[4000000] = ksm(fac[4000000],mod - 2);
for(int i = 3999999; i >= 0; -- i) inv[i] = inv[i + 1] * (i + 1) % mod;
if(k == 1) { puts("1"); return 0; }
dp[0][0] = 1;
for(int i = 1; i <= n; ++ i){
dp[i][0] = 1;
for(int j = 1; j <= i; ++ j){
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] * C(n * k - i - (j - 1) * (k - 1) - 1, k - 2) % mod * (n - j + 1) % mod ) % mod;
}
}
printf("%lld\n",dp[n][n]);
return 0;
}
原文链接: https://www.cnblogs.com/zzhzzh123/p/13344555.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
![H - Leftmost Ball](https://www.ccppcoding.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/368887
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!