正題

題目連接:http://www.51nod.com/Challenge/Problem.html#problemId=1836

---

題目大意

$n$個點$m$次隨機選擇一個點標記（可以重復），求最后被標記點的期望個數。

$1\le n,m\le 10^{18}$

---

解題思路

額開始拿方案數推了半天后面發現要斯特林數就放棄了，然后換了種方法發現很簡單？

設$i$輪之后被標記點的期望個數是$f_i$，那么有
$$f_i=f_{i?1}+\frac{n?f_{i?1}}{n}$$
$$f_i=f_{i?1}\frac{n?1}{n}+1$$
然后矩陣乘法就好了。

有一說一我第一次用期望值來算概率（（（

時間復雜度$O(T\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int S=2; 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 i=0;i<S;i++)for(int j=0;j<S;j++)for(int k=0;k<S;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(m&1)ans=ans*f;f=f*f;m>>=1;}printf("%.12lf\n",(double)ans.a[0][1]);}return 0; }

總結

以上是生活随笔為你收集整理的51nod1836-战忽局的手段【期望dp,矩阵乘法】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。