51nod 1836 战忽局的手段（期望）

Description

众所周知，有一个神秘的组织——战忽局，在暗中保护着我们。在局中任职的官员都有着极强的忽悠技巧，不只能用预言，还能用往事忽悠人。如今某外星间谍已经获得了战忽局曾经参与的n次事件的资料，局座发现了这件事，于是决定再次用忽悠来保证战忽局的安全。局座将发表m次演讲，每一天他都会从n事件中等概率地挑选一件混淆众人，由于局座每天很忙，不能把之前将的事件都记录下来，因此他可能会重复选择某一件事。现在局座想知道，m次演讲过后，期望能使多少事件混淆众人。

Input

第一行一个整数T（1<=T<=1000）,表示数据组数。接下来T行每行两个正整数n,m（1<=n,m<=1e18）分别表示事件数和局座演讲的次数。

Output

对于每组数据输出一行一个实数ans,表示局座在m次演讲之后期望混淆众人的事件数，你输入的数和标准答案的相对误差不超过1e-6视为正确。

Input示例

Output示例

1.5000000
10.0000000
1.6666667

思路

定义 $f_x$ 为 $n$ 个事件，忽悠 $x$ 次的期望事件数。

显然， $f_x=f_{x-1}+(1-\frac{f_{x-1}}{n})=1+\frac{n-1}{n}f_{x-1}$ 。

于是构造出矩阵：

$$ \begin{pmatrix} f_1 & 1 \\ 0 & 0 \end{pmatrix} \times \begin{pmatrix} \frac{n-1}{n} & 0 \\ 1 & 1 \end{pmatrix}^{m-1} $$

用快速幂简单写一下就好了，其中 $f_1=1$ 。

注意 long double 貌似精度也不够，可以用 __float128 。

AC 代码

#include<bits/stdc++.h>
#include<quadmath.h>
#define IO ios::sync_with_stdio(false);\
    cin.tie(0);\
    cout.tie(0);
using namespace std;
typedef long long LL;
typedef __float128 LB;
const int maxn = 1e8+10;

struct node
{
    LB mp[2][2];
} init,res;

struct node Mult(struct node x,struct node y)
{
    struct node tmp;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
        {
            tmp.mp[i][j]=0;
            for(int k=0; k<2; k++)
                tmp.mp[i][j]+=x.mp[i][k]*y.mp[k][j];
        }
    return tmp;
}

struct node expo(struct node x, LL k)
{
    struct node tmp;
    memset(tmp.mp,0,sizeof(tmp.mp));
    tmp.mp[0][0] = tmp.mp[1][1] = 1;
    while(k)
    {
        if(k&1) tmp=Mult(tmp,x);
        x=Mult(x,x);
        k>>=1;
    }
    return tmp;
}

void solve(LL n,LL m)
{
    init.mp[0][0] = LB(n-1) / n;
    init.mp[0][1] = 0;
    init.mp[1][0] = 1;
    init.mp[1][1] = 1;
    res = expo(init,m-1);
    cout<<fixed<<setprecision(12)<<double(res.mp[0][0]+res.mp[1][0])<<endl;
}

int main()
{
    IO;
    int T;
    cin>>T;
    while(T--)
    {
        LL n,m;
        cin>>n>>m;
        solve(n,m);
    }
    return 0;
}