【agc002f】Leftmost Ball

题目大意

有n种颜色，每种k个球。将这些球任意排列，将每种颜色中最前面的一个求涂成白色（就是n+1种颜色），求最终的排列的方案的个数。

解题思路

考虑如何计算不会算重，

按颜色顺序，每次往排列插入k个球，k-1个某种颜色，以及一个白球。

那么只要我们每次插入k个球时，保证白球一定在之前插入的白球的后面，并且某种颜色的第一个球，放在上一次的颜色的第一个球的后面，就可以保证不会算重，最后再乘个n！。

但是正着不好做，于是反过来插入，先插的n种颜色，dp一下，设f[i][j]表示放到第i种颜色，前面有j+1个白球（为啥是j+1？其实只是为了方便）。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

#include <map>

#include <bitset>

#include <set>

const int maxlongint=2147483647;

const long long mo=1e9+7;

const int N=2005;

using namespace std;

int n,k;

long long f[N][N],jc[N*N],ny[N*N],ans;

long long poww(long long x,int y)

{

	long long s=1;

	for(;y;y>>=1,x=x*x%mo)

		if(y&1) s=s*x%mo;

	return s;

}

long long C(int m,int n)

{

	if(n>m) return 0;

	return jc[m]*ny[n]%mo*ny[m-n]%mo;

}

int main()

{

	scanf("%d%d",&n,&k);

	if(k<=1)

	{

		printf("1\n");

		return 0;

	}

	jc[0]=ny[0]=1;

	for(int i=1;i<=n*k;i++) jc[i]=jc[i-1]*i%mo,ny[i]=poww(jc[i],mo-2);

	f[0][0]=1;

	for(int i=1;i<=n;i++)

		for(int j=i;j>=0;j--)

			f[i][j]=(f[i][j]+f[i-1][j-1]*C(k*i-j-1,k-2)%mo+f[i][j+1])%mo;

	printf("%lld",f[n][0]*jc[n]%mo);

}

巴特西

【agc002f】Leftmost Ball

题目大意

解题思路

最新文章

热门文章