【牛客 - 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

输出

复制

示例2

输入

复制

3 1
1 2 3

输出

复制

示例3

输入

复制

3 2
1 2 3

输出

复制

示例4

输入

复制

3 3
1 2 3

输出

复制

示例5

输入

复制

8 1
1 6 35 45 65 3 56 8

输出

复制

备注:

有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 ;
}