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]?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;
}

总结

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