本文共 2708 字，大约阅读时间需要 9 分钟。

问题E. Bet

赌钱，每个队都有对应的赔率，求最多能对多少个队下注，使得只要有一个队赢了就可以保证总是赚钱。

这个问题可以转化为一个概率问题。首先，我们需要将每个队的赔率转换为赢的概率。假设对第i个队下注了一份钱，占总下注金额的比例为p_i。通过赔率公式，可以得到p_i = A_i / (A_i + B_i)，其中A_i是赢的概率，B_i是输的概率。

为了保证只要有一个队赢，就能赚钱，我们需要确保所有可能的赢法的期望值之和大于1。假设对k个队下注，每个队的期望值为p_i * (1 + B_i)。只要这k个队的期望值之和大于1，就能满足条件。

为了最大化k，我们需要选择期望值最大的k个队，并累加它们的期望值。具体步骤如下：

例如，假设有n个队，每个队的p_i都已知，我们将它们从大到小排序，并选择前k个队。只要前k个队的期望值之和大于1，就可以保证赚钱。

答案即为排序后的前k个队的期望值之和大于1时的最大k值。

代码：

#include 
   
    
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
const int maxn=10005;
const int mod = 1e9+7;
using namespace std;
long double A[maxn];
ll ksm(ll a, ll b, ll m) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % m;
        b >>= 1;
        a = (a * a) % m;
    }
    return ans;
}
int main() {
    // freopen("D:\\input.txt", "r", stdin);
    // freopen("D:\\output.txt", "w", stdout);
    int t, n, m, k;
    cin >> t;
    for (int cas = 1; cas <= t; ++cas) {
        cin >> n >> m >> k;
        ll ans = 0;
        for (int i = 2; i <= k; ++i)
            ans = (ans + ksm(i - 1, m + n - 2, mod)) % mod;
        ans = ans * m % mod;
        ans = ans * n % mod;
        ans = (ans + ksm(k, (n-1)*(m-1), mod)) % mod;
        ans = (ans + ksm(k, n*m, mod)) % mod;
        cout << "Case #" << cas << ": " << ans << endl;
    }
    return 0;
}
   

问题H. Great Cells

这个式子可以拆分为两个部分：∑ g=0 到 NM (g+1) * A_g 和 ∑ g=0 到 NM A_g。前者可以进一步分解为 ∑ g=0 到 NM g * A_g + ∑ g=0 到 NM A_g。

对于后者，我们需要考虑所有可能的染色方案。每个格子可以用K种颜色染色，总共有K^{NM}种方案。每个Good点对应一种颜色选择，其数量为K种，且每个Good点的染色方案数为K^{NM}。

具体来说，对于第i个Good点，其染色方案数为K^{NM}。同时，非Good点的染色方案数为K^{NM}。因此，总染色方案数为K^{NM}。

对于前者，即∑ g=0 到 N*M g * A_g，考虑到每个Good点的贡献，可以计算为K^{NM}。

最终答案即为：

NM × K × (K-1)^{M-1} × N^{M-1} + K × (N-1)^{M-1} × M^{N-1} + K^{NM}

其中，NM为点总数，K为颜色种类数，N、M为格子的行列数。

代码：

#include 
   
    
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
const int maxn=10005;
const int mod = 1e9+7;
using namespace std;
long double A[maxn];
ll ksm(ll a, ll b, ll m) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % m;
        b >>= 1;
        a = (a * a) % m;
    }
    return ans;
}
int main() {
    // freopen("D:\\input.txt", "r", stdin);
    // freopen("D:\\output.txt", "w", stdout);
    int t, n, m, k;
    cin >> t;
    for (int cas = 1; cas <= t; ++cas) {
        cin >> n >> m >> k;
        ll ans = 0;
        for (int i = 2; i <= k; ++i)
            ans = (ans + ksm(i - 1, m + n - 2, mod)) % mod;
        ans = ans * m % mod;
        ans = ans * n % mod;
        ans = (ans + ksm(k, (n-1)*(m-1), mod)) % mod;
        ans = (ans + ksm(k, n*m, mod)) % mod;
        cout << "Case #" << cas << ": " << ans << endl;
    }
    return 0;
}