一个特别神奇的dp，特别厉害。
f(i, j) 表示 有 j 轮发动技能的牌在 [1, i] 另外的m - j轮在[i + 1, n]之间的概率。
怎么转移呢？
首先考虑i这张牌不选的情况，f(i - 1, j) 表示 j --> [1, i - 1] && m - j --> [i, n] (用箭头表示在[]之间...)，那么我们只需要让在[i, n]之间的m - j个选择都不是i即可，那么我们应该 * (1 - p[i]) ^ (m - j)
再考虑这张牌我们要选的情况，f(i - 1, j - 1)表示 j - 1 --> [1, i - 1] && m - j + 1 --> [i, n]， 那么我们需要m - j + 1中至少有一个i, 所以我们应该 * (1 - (1 - p[i]) ^ (m - j + 1))
所以就有了转移方程：
$\mbox{f(i, j) = f(i - 1, j) * (1 - p[i]) ^ {m - j} + f(i - 1, j - 1) * (1 - (1 - p[i]) ^ {m - j + 1})}$
那么初始条件是多少呢？ f(0, 0) == 1 为什么呢：
m次选择都在n之间的概率为1，那么f(n, m) == 1，这意味着m --> [1, n] 那么 另外的 0个选择--> 0，所以f(0, 0) == 1.
那么答案是多少呢？
应该是对于每一个扑克牌，我们扫描整个m轮，用当前的概率与扑克牌的贡献的成绩累加答案。
ans += d[i] * f[i - 1][j] * (1 - pow(1 - p[i], m - j)); 用j --> [1, i - 1] && m - j --> [i, n] 并且m - j中至少有一个i。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define mp make_pair
#define pb push_back
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second
using namespace std;
typedef long long i64;
typedef pair<int, int> pii;
const int inf = ~0U >> ;
const i64 INF = ~0ULL >> ;
//*********************************** long double p[]; int d[];
long double f[][]; int main() {
int T; scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
rep(i, , n) scanf("%Lf%d", &p[i], &d[i]);
memset(f, , sizeof(f));
f[][] = ;
rep(i, , n) {
rep(j, , m) f[i][j] = f[i - ][j] * pow( - p[i], m - j) + f[i - ][j - ] * ( - pow( - p[i], m - j + ));
}
long double ans();
rep(i, , n) {
rep(j, , m) {
ans += d[i] * f[i - ][j] * ( - pow( - p[i], m - j));
}
}
printf("%.10Lf\n", ans);
}
return ;
}
有一点还不太理解，就是在转移的时候，假如我们选取了i，那么用f(i - 1, j - 1)转移的时候乘的是至少有一个i的概率，那假如大于1个那么和题意不就矛盾了吗。。求助。。。