题意:
第0天有1个吸血鬼和n-1个人. 每天会有两个个体相遇. 异种, 则p的概率, 人变吸血鬼.
问给定p时, 人全部变成吸血鬼的天数期望.
思路:
概率DP.
求期望一般是倒着算. 加上组合数公式.
#include <cstdio> #include <cstring> using namespace std; const int MAXN = 1e5+5; double dp[MAXN],p; int n; int main() { int T; scanf("%d",&T); while(T--) { scanf("%d %lf",&n,&p); dp[n] = 0; for(int i=n-1;i>0;i--) { dp[i] = dp[i+1] + 1.0*n*(n-1)/(2.0*p*i*(n-i));//注意int转double处理细节 } printf("%.3lf\n",dp[1]); } }