51nod 1836 战忽局的手段

看了这个题的题解是真心佩服，学到了一招，之前对矩阵快速幂也只是知道，现在明仔了他的用法用在那里，这个题解是真的厉害，推导的完全虐到我这大学生（渣渣）,局座果然强，能忽悠。

令f[i][j]为i次忽悠中有j个事件的概率
显然f[i][j]=f[i-1][j]*j/n+f[i-1][j-1]*(n-j+1)/n
令g[i]为i次忽悠之后期望的事件数

我们考虑这个g[i]=(n-1)/n*g[i-1]+1这个递推式，可以矩阵加速
如下

             [(n-1)/n , 0]
[g[i],1]*|                 |=[g[i+1],1]

             [   1         , 1]

#include <bits\stdc++.h>
using namespace std;
const int MAXN=2;
struct Matrix
{
    __float128 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,long long  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);
    a=Multi(a,a);
 m/=2;
}
return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
    long long n,m;
    scanf("%lld%lld",&n,&m);
    Matrix a;
    a.mat[0][0]=(__float128)(n-1)/n;
    a.mat[0][1]=0;
    a.mat[1][0]=1;
    a.mat[1][1]=1;
    Matrix ans=Pow(a,m-1);//中间n-1次相乘
    __float128 tmp=ans.mat[0][0]+ans.mat[1][0];//第一次是【1,1】
    double res=tmp;
    printf("%.12f\n",res);
    }
    return 0;
}