汕头做网站公司哪家好,discuz二次开发,汕头站扩建招标,免费一级域名解析正题
题目连接:http://www.51nod.com/Challenge/Problem.html#problemId1836 题目大意 nnn个点mmm次随机选择一个点标记#xff08;可以重复#xff09;#xff0c;求最后被标记点的期望个数。 1≤n,m≤10181\leq n,m\leq 10^{18}1≤n,m≤1018 解题思路
额开始拿方案数推了…正题
题目连接:http://www.51nod.com/Challenge/Problem.html#problemId1836 题目大意
nnn个点mmm次随机选择一个点标记可以重复求最后被标记点的期望个数。
1≤n,m≤10181\leq n,m\leq 10^{18}1≤n,m≤1018 解题思路
额开始拿方案数推了半天后面发现要斯特林数就放弃了然后换了种方法发现很简单
设iii轮之后被标记点的期望个数是fif_ifi那么有 fifi−1n−fi−1nf_if_{i-1}\frac{n-f_{i-1}}{n}fifi−1nn−fi−1 fifi−1n−1n1f_if_{i-1}\frac{n-1}{n}1fifi−1nn−11 然后矩阵乘法就好了。
有一说一我第一次用期望值来算概率
时间复杂度O(Tlogn)O(T\log n)O(Tlogn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int S2;
struct Matrix{__float128 a[S][S];
}f,ans,c;
long long T,n,m;
Matrix operator*(const Matrix a,const Matrix b){c.a[0][0]c.a[0][1]c.a[1][0]c.a[1][1]0;for(int i0;iS;i)for(int j0;jS;j)for(int k0;kS;k)c.a[i][j]a.a[i][k]*b.a[k][j];return c;
}
int main()
{scanf(%lld,T);while(T--){scanf(%lld%lld,n,m);f.a[1][1](__float128)(n-1)/n;f.a[0][1]f.a[0][0]1;f.a[1][0]0;ans.a[0][0]1;ans.a[0][1]0;while(m){if(m1)ansans*f;ff*f;m1;}printf(%.12lf\n,(double)ans.a[0][1]);}return 0;
}
