Contest Setting（动态规划，求方案数）_动态规划 取数 方案数

原题链接

题意

题目可以转化为，$n$种不同的物品，每种有$w[i]$个，问用这些物品中选k种，能有多少种组合方式，每一种组合中的物品必须各不相同，问总共可以有多少种组合方案。

思路

定义$f[i][j]$为用前i种物品,每$j$个一组的所有组合方案数。
首先，因为要求的是组合方式，所以，应该用，乘法，既然要用乘法，那么初始化，肯定得是1，也可以理解为所有物品一个都不选时为一种方案。

然后我们通过推导得出用前i种物品$j$个一组时可以由用前$i-1$种物品$j-1$个一组时的所有方案得到，用前$i-1$种物品$j-1$个一组时的所有方案数*当前第$i$个物品的数量，就是用第$i$种物品$j$个一组时的所有方案数，然后加上用$i-1$种物品，$j$个一组时的所有方案数可以得到 用前i种物品j个一组时的所有方案数。得出状态转移方程$$f[i][j]=f[i-1][j-1]\ast w[i]+f[i-1][j]$$

如果有所遗忘那就看看我的手记吧

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1005, mod = 998244353;

int a[N] ;
int f[N][N];
int n, k;
int cnt = 1;
map<int, int> res;
int w[N];

signed main()
{
	cin >> n >> k;
	
	for (int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
		res[a[i]] ++;
	}
	
	for (auto i : res)
	{
		w[cnt ++ ] = i.second;
	}
	cnt --;
//	for (int i = 1; i <= cnt; i ++ ) cout << w[i] << " ";
	
	//初始化应从0开始 
	for (int i = 0; i <= cnt; i ++ ) f[i][0] = 1;
	
	for (int i = 1; i <= cnt; i ++ )
	{
		for (int j = 1; j <= k; j ++ )
		{
			f[i][j] = f[i - 1][j - 1] * w[i] % mod + f[i - 1][j];
			f[i][j] %= mod;
		}
//		for (int j = 1; j <= k; j ++ )
//		{
//			cout << f[i][j] << " ";
//		}
//		cout << endl;
	}
	cout << f[cnt][k] % mod << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

总结

还是练得不够多，思维跟不上啊。