传送门
题目描述：
众所周知，有一个神秘的组织——战忽局，在暗中保护着我们。在局中任职的官员都有着极强的忽悠技巧，不只能用预言，还能用往事忽悠人。
如今某外星间谍已经获得了战忽局曾经参与的n次事件的资料，局座发现了这件事，于是决定再次用忽悠来保证战忽局的安全。局座将发表m次演讲，
每一天他都会从n事件中等概率地挑选一件混淆众人，由于局座每天很忙，不能把之前将的事件都记录下来，因此他可能会重复选择某一件事。
现在局座想知道，m次演讲过后，期望能使多少事件混淆众人。
Input
第一行一个整数T（1<=T<=1000）,表示数据组数。接下来T行每行两个正整数n,m（1<=n,m<=1e18）分别表示事件数和局座演讲的次数。
Output
对于每组数据输出一行一个实数ans,表示局座在m次演讲之后期望混淆众人的事件数，你输入的数和标准答案的相对误差不超过1e-6视为正确。
Input示例
3 2 2 10 100000 3 2
Output示例
1.5000000 10.0000000 1.6666667
解题思路：
令 fi 为第 i 次忽悠之后期望的事件数，那么就有两种可能，一种是下一次选的事件是以前忽悠过的，这个的概率就是 fin，
另一种就是选的事件是以前没有忽悠过的，那么这个的概率就是 n−fin 那么我们可以列出期望方程：
fi+1 =finfi+n−fin(fi+1)
然后将上述式子整理发现：
fi+1 = n−1n∗fi+1 ， 然后就根据矩阵快速幂就可以解决时间的问题了，但是还有一个问题就是，精度不够，又学了一个黑科技
__float128， 用这个就可以解决精度的问题了，然后就可以 AC 了。
My Code：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; typedef long long LL; typedef __float128 fff; const int MAXN = 2; struct Matrix{ fff mat[MAXN][MAXN]; }; Matrix Multi(Matrix a, Matrix b){ Matrix c; for(int i=0; i<MAXN; i++){ for(int j=0; j<MAXN; j++){ c.mat[i][j] = 0; for(int k=0; k<MAXN; k++) c.mat[i][j] += a.mat[i][k]*b.mat[k][j]; } } return c; } Matrix Pow(Matrix a, LL m){ Matrix ans; memset(ans.mat, 0, sizeof(ans.mat)); ans.mat[0][0] = ans.mat[1][1] = 1; while(m){ if(m & 1) ans = Multi(ans, a); m>>=1LL; a = Multi(a, a); } return ans; } int main(){ int T; scanf("%d",&T); while(T--){ LL n, m; scanf("%lld%lld",&n,&m); Matrix a; a.mat[0][0] = (fff)(n-1)/n; a.mat[0][1] = 0; a.mat[1][0] = 1; a.mat[1][1] = 1; Matrix ans = Pow(a, m-1); fff tmp = ans.mat[0][0] + ans.mat[1][0]; double res = tmp; printf("%.12lf\n",res); } return 0; }