本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-12 21:22:29

【题目链接】

题解思路：

我们把 $k$ 视为单位一，最后乘上就行。

定义 $f_{i,j}$ 为还剩 $i$ 轮，需要做 $m$ 次加法的结果。有 $f_{i , i} = i$，$f_{i , 0} = 0$。这是边界情况。

另外当 $i > j > 0$ 时： $$f_{n , m} = \min (-x + f_{n - 1 , m - 1} , x + f_{n - 1 , m})(0 \le x \le 1)$$

得

$$\max_{x}f_{n , m} = \frac{f_{n-1 ,m-1}+f_{n - 1 , m}}{2} $$

至此，我们可以 $O(nm)$ 的 DP 解决 D1 的数据。

AC Code:

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int Maxn = 2010;
const int N = 2000;
const int mod = 1e9 + 7;
int f[Maxn][Maxn];
ll power (ll a , ll x) {
    ll r = 1;
    a %= mod;
    while (x) {
        if (x & 1) r = r * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return r;
} 
ll inv (ll a) {
    return power (a , mod - 2);
}
void solve () {
    ll n , m , k;
    cin >> n >> m >> k;
    cout << f[m][n] * k % mod << endl;
}
int main() {
    ll i2 = inv (2);
    for (int i = 1; i <= N; ++ i) {
        f[i][i] = i;
        for (int j = i + 1; j <= N; ++ j) 
            f[i][j] = (f[i][j - 1] + f[i - 1][j - 1]) % mod * i2 % mod;
    }
    int T;
    cin >> T;
    while (T --) {
        solve ();
    }
    return 0;
}