题解 | 小红又战小紫

关于，我们有公式

so

对本题而言，显然在全1时必胜，不是全1时肯定选策略1

那么记录1的个数sum1，2的个数sum2，显然当前的胜率与和有关

那么取递归函数win表示当前赢的概率，参数分别为1的个数和2的个数，根据递归关系计算即可（返回值为分子分母）

（记得存已计算的值，不然重复递归会TLE）

#include <iostream>
#include <cstdio>
using namespace std;
#define LL long long

const LL mod = 1e9 + 7;

pair<LL,LL> f[1001][1001];

LL qpow(LL x, LL y)
{
    LL a = 1;
    x %= mod;
    while (y)
    {
        if (y&1) a = a * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return a;
}

pair<LL, LL> win(LL sum1, LL sum2)
{
    if (sum1 < 0)
        return {0l, 1l};
    if (sum2 == 0)
        return {1l, 1l};
    if (f[sum1][sum2].second != 0l)
        return f[sum1][sum2];
    //{sum1, (sum1 + sum2)%mod}, {sum2, (sum1 + sum2)%mod}
    pair<LL, LL> p1 = win(sum1-1, sum2), p2 = win(sum1+1, sum2-1), p3, p4;
    if (sum1 == 0)
        p3 = {0l, 1l};
    else
        p3.first = (p1.second-p1.first + mod) * sum1 % mod, p3.second = p1.second * (sum1 + sum2)%mod;
    p4.first = (p2.second-p2.first + mod) * sum2 % mod, p4.second = p2.second * (sum1 + sum2)%mod;

    f[sum1][sum2] = {(p3.first*p4.second%mod + p3.second*p4.first%mod)%mod, 
                p3.second*p4.second%mod};
    return f[sum1][sum2];
}

int main() 
{
    int n, a;
    LL sum1=0, sum2=0;
    cin >> n;
    for (int i=0; i <n; i ++)
    {
        cin >> a;
        if (a == 1)sum1++;
        else sum2++;
        f[i][0] = {1l, 1l};
        for (int j=1; j <n; j ++)
            f[i][j] = {0l, 0l};
    }
    f[0][0] = {0l, 1l};

    pair<LL,LL> ret = win(sum1, sum2);
    //cout << ret.first << " " << ret.second << endl;
    LL ans = qpow(ret.second, mod-2) * ret.first % mod;
    printf ("%lld\n", ans);
    return 0;
}