牛客周赛 Round 29 F.小红又战小紫【概率dp】

原题链接：https://ac.nowcoder.com/acm/contest/73422/F

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

小红上次输给了小紫，表示不服，于是又约来小紫来玩一个游戏。
这次是取石子游戏：共有n堆石子，两人轮流使用以下两种技能中的一种进行取石子：
1. 随机选择某一堆石子，取走其中的一颗石子。
2. 每一堆石子各取走一颗石子。
小红先手，谁先取完所有的石子谁获胜。两人都希望自己的获胜概率尽可能高，假设两人都绝顶聪明，请你计算小红最终获胜的概率。

输入描述:

第一行输入一个正整数n，代表石子的堆数。
第二行输入n个正整数ai?，代表每一堆石子的数量。
1≤n≤1000
1≤ai≤2

输出描述:

一个整数，代表小红最终获胜的概率对1e9+7取模的值。可以证明，最终的答案一定是个有理数，你只需要输出其对1e9+7取模的结果。
分数取模的定义：假设答案是x/y，那么其对p取模的答案是找到一个整数a满足a∈[0,p-1]且a?y对p取模等于x。

示例1

输入

2
1 2

输出

500000004

说明

显然小红会使用 1 技能，因为如果使用 2 技能则必输。
小红有1/2的概率取走第一堆石子的 1 颗（此后无论小紫怎么取，小红必胜），有1/2的概率取走第二堆石子的 1 颗（此时小紫只需要直接使用 2 技能则获胜，小红失败），因此小红最终获胜的概率是 1/2。因为 500000004*2=1000000008，对1e9+7取模恰好等于1，所以输出 500000004。

解题思路：

经典概率dp,首先题目说了要求小红获胜的概率，而小红是先手也就是要求先手获胜的概率。首先我们可以发现几个明显的性质。

性质1：如果不存在石子数为2的石堆那么先手必胜。

性质2：如果存在石子数为2的石堆那么肯定会使用技能1，也就是只从某一堆拿走一个，因为这个时候如果使用技能2那么当前先手必败，他足够聪明那么必然会使用技能1。

对于性质1可以用于初始化，根据性质2我们可以知道游戏过程中的操作实际就只有俩种了，这俩种操作是要么从石子数为1的那堆石子拿一个，要么从石子数为2的那堆石子拿一个。

知道了上面这俩个性质就可以考虑dp了。

状态定义：

定义d[i][j]表示当前总的石子堆数为i，石子数为2的石子堆数为j时先手获胜的概率，此时石子数为1的石子堆数可以通过i-j计算出来。

初始化：

f[i][0]=1，没有石子数为2的石子堆，先手必胜

状态转移:

(1)在一个石子数为1的石堆中拿掉一个石子，首先拿到石子数为1的石堆所占比例为(i-j)/i，然后f[i-1][j]就表示后手获胜的概率了，1-f[i-1][j]才是先手获胜的概率，inv(i)表示i的逆元。

(i-j)*inv(i)*(1-f[i-1][j])

(2)在一个石子数为2的石堆中拿掉一个石子，首先拿到石子数为2的石堆所占比例为j/i，然后f[i][j-1]就表示后手获胜的概率了，1-f[i][j-1]才是先手获胜的概率，inv(i)表示i的逆元。

j*inv(i)*(1-f[i][j-1])

最终答案

最终答案就是f[n][c[2]]，c[2]表示石子数为2的石堆个数。

时间复杂度：dp第一维枚举为O(n),第二位枚举也为O(n),然后求逆元为O(logn)，所以最终时间复杂度为O((n^2)*log(n)),n=1000,时间大概是1e7,这个时间复杂度是可以过的，如果我们预处理逆元，那么每次求逆元就是O(1)了，那么时间复杂度可以优化到O(n^2),也就是把二维循环里面的求逆元，先在外面预处理好，在时间要求更高时可以考虑这样优化，这也是常用的一种优化方式。

空间复杂度：dp数组f空间为二维，所以最终空间复杂度为O(n^2),n=1000,所以空间大概是1e6*4/1e6=4M,大概也就4M,题目给了俩百多M,空间是肯定足够的。

cpp代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N=1010,mod=1e9+7;
int n;
int c[3];  //记录石子数为1的石子堆数和石子数为2的石子堆数
int f[N][N];

int qmi(int x,int k) //快速幂求逆元
{
    int res=1;
    while(k){
        if(k&1)res=(LL)res*x%mod;
        x=(LL)x*x%mod;
        k>>=1;
    }
    return res;
}
int inv(int x)  //求逆元
{
    return qmi(x,mod-2);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        c[x]++;
    }
    
    //dp处理过程
    for(int i=0;i<=n;i++)
    {
        f[i][0]=1;
        for(int j=1;j<=i;j++)
        {
            //题目要求输出的是和逆元有关，这里把除法写为逆元
            f[i][j]=(LL)(i-j)*inv(i)%mod*((1-f[i-1][j]+mod)%mod)%mod+(LL)j*inv(i)%mod*((1-f[i][j-1]+mod)%mod)%mod;
            f[i][j]%=mod;
        }
    }
    //输出答案
    cout<<f[n][c[2]]<<endl;
    return 0;
}