CF1628D1

FiraCode · 2022-04-12 21:22:29 · 个人记录

【题目链接】

题解思路：

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

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

另外当 i > j > 0 时：

得

至此，我们可以 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;
}