本题是一个计数类的问题，其中需要有一些优化。
简单思路
从题面和数据范围，可以猜测算法时间复杂度大概是\(O(nk)\)，所以不难想到用动态规划：
设\(f(i,j)\)为前\(i\)个数中选\(j\)个的总价值
则状态转移方程为
即当前不选\(a_i\)或者选\(a_i\)两种决策
接下来说方案数，方案数是做分母，在取模时需要求逆元，又\(19260817\)是一个质数，可以用费马小定理求逆元
方案数的求法可以根据求总价值的思路，新定义一个状态来转移，但本题可以有更好的
求方案数
不难发现，方案数问题实际上是这样一个新问题：
给定一个序列\(1,2,\cdots,n\)，取其中\(k\)个数\(a_1,a_2,\cdots,a_k\)，并且\(a_1\le a_2 \le \cdots \le a_k\)，求方案数（1）
这是一个经典问题，如果是\(C_n^m\)，则在上面修改为\(a_1< a_2 < \cdots < a_k\)
所以我们设\(b_1=a_1,b_2=a_2+1,\cdots,b_k=a_k+k-1\)，则（1）变为一个序列\(1,2,\cdots,n+k-1\)，取其中\(k\)个数\(b_1,b_2,\cdots,b_k\)，并且\(b_1< b_2 < \cdots < b_k\) ，求方案数
则方案数变成了\(C^{k}_{n+k-1}\)，可以利用线性求逆元求出
代码
我们先看一份\(30\)分的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+1e3,K=3e2+5;
const ll P=19260817;
int n,k;
ll a[N],f[N][K];
ll qpow(ll a,ll b) {
ll res=1;
while(b) {
if(b&1)
res=res*a%P;
a=a*a%P;
b>>=1;
}
return res;
}
ll inv[N],fac[N],fac_inv[N];
void init() {
fac[0]=fac_inv[0]=1;
inv[1]=fac[1]=fac_inv[1]=1;
for(int i=2;i<=n+k;i++) {
inv[i]=(P-P/i)*inv[P%i]%P;
fac[i]=i*fac[i-1]%P;
fac_inv[i]=inv[i]*fac_inv[i-1]%P;
}
}
ll C(int n,int m) {
return fac[n]*fac_inv[m]%P*fac_inv[n-m]%P;
}
int main() {
scanf("%d%d",&n,&k);
init();
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)
f[i][1]=(f[i-1][1]+a[i])%P;
for(int j=2;j<=k;j++)
for(int i=1;i<=n;i++)
f[i][j]=(f[i-1][j]+a[i]*f[i][j-1]%P)%P;
printf("%lld\n",f[n][k]*qpow(C(n+k-1,k),P-2)%P); //利用费马小定理求逆元
return 0;
}
发现有好多点MLE了，这是因为\(f\)数组虽然时间复杂度\(O(nk)\)过得去，但是空间复杂度太大了，再观察状态转移方程，发现只从本层和上一层转移，所以可以使用滚动数组进行优化
最终AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,K=3e2+2;
const ll P=19260817;
int n,k;
ll a[N],f[2][N];
ll qpow(ll a,ll b) {
ll res=1;
while(b) {
if(b&1)
res=res*a%P;
a=a*a%P;
b>>=1;
}
return res;
}
ll inv[N+K],fac[N+K],fac_inv[N+K];
void init() {
fac[0]=fac_inv[0]=1;
inv[1]=fac[1]=fac_inv[1]=1;
for(int i=2;i<=n+k;i++) {
inv[i]=(P-P/i)*inv[P%i]%P;
fac[i]=i*fac[i-1]%P;
fac_inv[i]=inv[i]*fac_inv[i-1]%P;
}
}
ll C(int n,int m) {
return fac[n]*fac_inv[m]%P*fac_inv[n-m]%P;
}
int main() {
scanf("%d%d",&n,&k);
init();
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
int cur=1;
for(int i=1;i<=n;i++)
f[cur][i]=(f[cur][i-1]+a[i])%P;
for(int j=2;j<=k;j++) {
cur^=1; //滚动数组
memset(f[cur],0,sizeof(f[cur])); //清除数组
for(int i=1;i<=n;i++)
f[cur][i]=(f[cur][i-1]+a[i]*f[cur^1][i]%P)%P;
}
printf("%lld\n",f[cur][n]*qpow(C(n+k-1,k),P-2)%P);
return 0;
}