【牛客 - 696D】小K的雕塑（dp，鸽巢原理，01背包类问题）
题干：
链接：https://ac.nowcoder.com/acm/contest/696/D
来源：牛客网
小K有n个雕塑，每个雕塑上有一个整数
若集合T中的每一个元素在n个雕塑上都能找得到，则称这个集合为一个优秀的集合
小K想知道所有大小<=k优秀的集合的价值和是多少
一个优秀的集合的价值可以用
输入描述:
两个整数n,k，分别表示雕塑的数量与集合大小的上限 接下来n个整数表示第i个雕塑上的数字aiai是多少
输出描述:
一行表示所有大小<=k优秀集合的权值和
示例1
输入
3 0 1 2 3
输出
1
示例2
输入
3 1 1 2 3
输出
7
示例3
输入
3 2 1 2 3
输出
18
示例4
输入
3 3 1 2 3
输出
24
示例5
输入
8 1 1 6 35 45 65 3 56 8
输出
220
备注:
有10%10%的数据满足k=1
有30%30%的数据满足k=n
以上两个部分包含在100%100%的数据中，但不包含在前30%30%的数据中
对于前30%30%的数据，满足k≤n≤5k≤n≤5
对于100%100%的数据，满足n≤106,1≤ai≤5×103n≤106,1≤ai≤5×103
由于答案可能过大请对109+7取模后输出
解题报告：
题意好难懂啊、、、
注意到集合的性质：互异性。
根据鸽巢原理，很容易知道最多有m=5e3个数（去重之后）
然后设F[n][k]表示前n个数，取k个数的价值。（且已知这k个数一定互不相同。因为集合的互异性）
F[n][k]=F[n-1][k]+F[n-1][k-1]*a[i]
效率O(m^2)。
当然这题也可以用01背包的方法将空间复杂度优化到一维。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 1e6 + 5;
const ll mod = 1e9+7;
ll dp[5005][5005];
int a[MAX],b[MAX];
int n,k;
int main()
{
cin>>n>>k;
for(int i = 1; i<=n; i++) cin>>a[i],b[i]=a[i];
sort(b+1,b+n+1);
int N = unique(b+1,b+n+1) - b - 1;
dp[0][0]=1;
for(int i = 1; i<=N; i++) {
dp[i][0] = 1;
for(int j = 1; j<=k; j++) {
dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] * b[i])%mod;
}
}
ll ans = 0;
for(int i = 0; i<=N && i<=k; i++) ans = (ans + dp[N][i])%mod;
cout << ans << endl;
return 0 ;
}
