蒟蒻笔者正试探地迈出写 DP 题解的第一步。
首先，分析题意。
这道题就是说，要在 n 个数里选 k 个数，把它们乘起来，最后再把所有这些积加起来。（见样例解释 #2）
很容易可以发现这是个 DP，而且和 01 背包非常相似（因为每个数只能选一次），尤其和求方案数的做法相似。（好像楼下有几个大佬已经提过了）
如果令 (dp[i][j]) 表示前i个数字选j个的得分。
容易有 (dp[i][j]=dp[i-1][j]+dp[i-1][j-1] imes a[i])。其中(1le i le n , 1le j le k)。
答案就是 (dp[n][k])。
但是这个做法我想出来之后立马就被数据范围 Hank 掉了。
所以我又想到01背包降维打击（非物理），倒序循环k优化。
说白了，就是省掉第一维，然后倒序防止重复选。
这样虽然还是双重循环，但是空间已经是一维了，这样就可以过掉此题。
答案当然是 (dp[k])。
应该来看这篇题解的dalao都应当是学过背包了，但是还是放一下背包DP罢。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=1000000007;
int n,k;
int dp[100005],a[100005];
signed main() {
cin>>n>>k;
dp[0]=1;
for(int i=1; i<=n; i++)
cin>>a[i];
for(int i=1; i<=n; i++) {
for(int j=k; j; j--) {
dp[j]=(dp[j]+dp[j-1]*a[i])%M;
}
}
cout<<dp[k];
return 0;
}