题解 | 小红叒战小紫

#include <bits/stdc++.h>
const int mod = 1E9 + 7;
using namespace std;
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m;
    int a = 0, b = 0;
 
    int w;
 
    std::cin >> n >> m;
    for (int i = 0; i < n; ++i) std::cin >> w, a += w == 1;
    for (int i = 0; i < m; ++i) std::cin >> w, b += w == 1;
    int  c = n - a, d = m - b;
 
    std::function<int(int)> get_inv = [](int v)->int {
        int p = mod - 2;
        int inv = 1;
        while (p) {
            if (p & 1) inv = 1ll * inv * v  % mod;
            v = 1ll * v * v % mod;
            p >>= 1;
        }
        return inv;
    };
 
    int dp[51][51];
    dp[0][0] = dp[a][b] = 0;
 
    if (a != n || b != m) {
        for (int i = 1; i <= a; ++i) {
            int inv = get_inv(i);
            dp[i][0] = (1 + 1ll * c * inv % mod + dp[i - 1][0]) % mod;
        }
 
        for (int i = 1; i <= b; ++i) {
            int inv = get_inv(i);
            dp[0][i] = (1 + 1ll * d * inv % mod + dp[0][i - 1]) % mod;
        }
 
        for (int i = 1; i <= a; ++i) {
            for (int j = 1; j <= b; ++j) {
                int inv = get_inv(i * d + j * c);
                dp[i][j] = 1ll * inv * (((i + c) * (j + d) + 1ll * i * d * dp[i - 1][j] % mod) % mod + 1ll * c * j * dp[i][j - 1] % mod) % mod;
            }
        }
    }
    std::cout << dp[a][b];
    return 0;
}

————————————————————————————————————————————————————————————————
期望Dp，显然这是个马尔科夫过程，对于每一次的选择，不影响下一次的双方选牌，使用条件概率求解期望即可。注意到当双方有一方全为0时连比都不用比，直接输出即可。由于期望值里边有个分式还要要取模，涉及一个逆元求解问题，手玩了下发现这个逆元比较大，不要用线性递推直接用费马小定理求。