P1921 赌博游戏

    • 84通过
    • 269提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 数论,数学
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    赌场是暴利的。大赌场通过游戏规则控制游戏的公平来赚钱。虽然规则看似很公平,但实际上是稍微有点不公平的,而大赌场由于客流量大,资金流量大,这点稍微的不公平就被放大到能让赌场得到很可观的收入。同时,这些个不公平有时并不是规则的不公平,而是道具不公平。比如说灌铅的骰子,它和正常骰子不一样,它投出Q种点数的概率并不一样。有时,为了不让顾客察觉,他们每一次游戏结束后都有可能更换骰子。

    题目描述

    作弊的赌场有N个骰子,在这个赌场可能发生了M次游戏,每次游戏包括一个骰子投出的点数,我们并不知道这个骰子的编号,但知道第i次游戏投出的点数O(i)。

    第i个骰子投出点数j的概率是A(i,j),用完第i个骰子,下一次用第j个骰子的概率为B(i,j)。特别地,对于第一次游戏,用第i个骰子的概率为π(i)。

    好奇的小v来问你,在这个赌场发生这M次游戏的概率。

    输入输出格式

    输入格式:

    第一行两个正整数N,M,Q

    第二行N个浮点数,表示π(i)

    第三行至2+N行有N*Q个浮点数,第i+2行j列表示A(i,j)

    第N+3至2*N+2行有N*N个浮点数,第N+2+i行j列表示B(i,j)

    第2*N+3行有M个正整数,表示M次游戏的结果O[i],也就是每次游戏投出的点数。

    输出格式:

    表示所求概率,保留四位位小数。

    输入输出样例

    输入样例#1: 复制
    3 10 3
    1 0 0
    0.03 0.03 0.94
    0.02 0.02 0.96
    0.99 0.005 0.005
    0.01 0.99 0
    0.05 0.05 0.90
    0.98 0.002 0.008 
    2 2 0 2 2 0 2 2 0 2
    
    输出样例#1: 复制
    0.4483

    说明

    数据范围:

    对于30%的数据:M<=100,1<=N,Q<=10

    对于100%的数据:1<=M<=1000,1<=N,Q<=50

    对于矩阵A,B,向量π都具备概率转移的特征条件

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。