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

发布时间:2024年01月22日

原题链接: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;
}
文章来源:https://blog.csdn.net/lianxuhanshu_/article/details/135752429
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。