#P1921. 赌博游戏【数据有误】

赌博游戏【数据有误】

题目背景

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

题目描述

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

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

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

输入格式

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

第二行 NN 个浮点数,表示 π(i)\pi(i)

第三行至 2+N2+N 行有 N×QN\times Q 个浮点数,第 i+2i+2jj 列表示 A(i,j)A(i,j)

N+3N+32×N+22\times N+2 行有 N×NN\times N 个浮点数,第 N+2+iN+2+ijj 列表示 B(i,j)B(i,j)

2×N+32\times N+3 行有 MM 个正整数,表示 MM 次游戏的结果 OiO_i,也就是每次游戏投出的点数。

输出格式

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

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

0.4483

提示

数据范围及约定

  • 对于 30%30\% 的数据:M100M \le 1001N1 \le NQ10Q \le 10
  • 对于 100%100\% 的数据:1M10001 \le M \le 10001N1 \le NQ50Q \le 50

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