#P6766. [2019备战noi]社会人

    ID: 6586 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>图论强连通分量CF2500状压DP概率DP数学矩阵并查集最短路

[2019备战noi]社会人

社会人

题目描述

有一个 nn 行 mm 列的网格点图。对于每一对上下或左右相邻的格点,独立地以概率 pp 不连边、以概率 1−p1-p 连一条无向边。

求左上角格点 (1,1)(1,1) 与右下角格点 (n,m)(n,m) 连通的概率。

若两个端点是同一个格点,则连通概率为 11。

输入格式

第一行一个正整数 TT,表示数据组数。

接下来 TT 行,每行两个正整数 n,mn,m 和一个实数 pp,表示一组数据。

输出格式

每组数据输出一行一个实数,表示所求概率。与标准答案的绝对误差不超过 10−610^{-6} 即可。

样例输入

3
2 2 0.5
3 2 0.7
1 1 0.2

样例输出

0.4375
0.0768204
1

数据范围

所有数据满足 1≤n≤81\le n\le8,1≤m≤10181\le m\le10^{18},1≤T≤501\le T\le50,0.1≤p≤10.1\le p\le1。

70%70\% 的数据满足 n,m≤4n,m\le4。