题解：P5131 荷取融合

___Mitsui_Hisashi___ · 2026-07-23 16:09:41 · 题解

Description

定义一次操作为在 n 个数中任选 k 个（可以重复），其收益为这 k 个数的积。求所有操作收益的平均值。

Analysis

先来观察操作次数。在 n 个不同的数中可重复地选 k 个，则方案为：

接下来来看总收益。记 dp_{i,j} 表示前 j 个选 i 个的所有乘积之和。对于最后一项在 j 处的情况，可以分两类进行讨论：

• 最后一个不是 j，即只能从前 j-1 个选。和为 dp_{i,j-1}。
• 最后一个是 j，即前 i-1 个选自 1\sim j，其乘积 dp_{i-1,j} 再乘上本次的 a_j，即为和。

故 dp_{i,j}\larr dp_{i,j-1}+a_j\cdot dp_{i-1,j}。边界条件为 dp_{0,j}=1，即选 0 个的乘积恒为 1。那么综合即为 dp_{k,n}。

但由于 n\le10^5,k\le300，k\times n 的数组会超内存限制。注意到 dp_{i} 的递推仅依赖于 dp_{i-1} 的值，因此可以使用滚动数组进行优化。

时间复杂度 \mathcal O(nk)，主要在总收益的计算上。

Code

#include"bits/stdc++.h"
#define int long long
using namespace std;
const int N = 2e5 + 5, mod = 19260817;
int n, k, a[N];
int dp[2][N];
int fac[N], inv[N];
int fpow(int a, int b) {
    int re = 1;
    while (b) {
        if (b & 1)
            re = re * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return re;
}
void init() {
    fac[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = fac[i - 1] * i % mod;
    inv[N - 1] = fpow(fac[N - 1], mod - 2);
    for (int i = N - 2; ~i; i--)
        inv[i] = inv[i + 1] * (i + 1) % mod;
}
int C(int n, int m) {
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    init();
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        dp[1][i] = 1;
    int cur = 1;
    for (int i = 1; i <= k; i++) {
        cur ^= 1;
        for (int j = 1; j <= n; j++) 
            dp[cur][j] = (dp[cur][j - 1] + a[j] * dp[cur ^ 1][j]) % mod;
    }
    cout << fpow(C(n + k - 1, k), mod - 2) * dp[cur][n] % mod;
    return 0;
}