2023-01-16

题目传送门

翻译

难度&重要性(1~10):3

题目来源

AtCoder

题目算法

dp

解题思路

因为蓝球的数量是固定的，题目让我们求，在取 \(i\) 次的情况下，有几种方案，首先我们肯定要枚举 \(i\)，范围就是 \(\sum_{i=1}^{k}\) 了，然后因为他每次只能取连续的蓝球，于是我们就可以想到用插板法求把蓝球分成 \(i\) 份有多少种情况，也就是求在 \(k-1\) 个空中插 \(i-1\) 个板子，就是求 \({k-1}\choose{i-1}\)，然后我们要把这 \(i\) 份蓝球插到 \(n-k\) 个红球中，注意这里有一点不一样，红球的两边都可以插蓝球，所以这里就可以转换为在 \(n-k+1\) 个空中插 \(i\) 个板子，就是求 \({n-k+1}\choose{i}\)，那么答案就可以写成 \(\sum_{i=1}^{k}{{k-1}\choose{i-1}}{{n-k+1}\choose{i}}\)，这个算法的时间复杂度为 \(O(n^2+k)\)。

完成状态

已完成

Code

#include<bits/stdc++.h>
using namespace std;
long long c[2005][2005],Mod=1e9+7,n,k,num;
int main(){
	cin>>n>>k;
	c[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%Mod;
	num=n-k;
	for(long long i=1;i<=k;i++)
		cout<<(c[num][i]*2+c[num][i-1]+c[num][i+1])%Mod*c[k][i]%Mod<<endl;
	return 0;
}