2017 ACM-ICPC 亚洲区（西安赛区）网络赛 Coin 矩阵快速幂

Bob has a not even coin, every time he tosses the coin, the probability that the coin's front face up is \frac{q}{p}(\frac{q}{p} \le \frac{1}{2})pq(pq≤21).

The question is, when Bob tosses the coin kktimes, what's the probability that the frequency of the coin facing up is even number.

If the answer is \frac{X}{Y}YX, because the answer could be extremely large, you only need to print (X * Y^{-1}) \mod (10^9+7)(X∗Y−1)mod(109+7).

Input Format

First line an integer TT, indicates the number of test cases (T \le 100T≤100).

Then Each line has 33 integer p,q,k(1\le p,q,k \le 10^7)p,q,k(1≤p,q,k≤107) indicates the i-th test case.

Output Format

For each test case, print an integer in a single line indicates the answer.

样例输入

样例输出

500000004

555555560
题意：给定n,m,k，每次抛一个硬币为正面朝上的概率为(m/n)，求抛k次硬币之后，硬币朝上的概率为多少（这里输出的是逆元之后的结果，所以很大）
题解：我们把概率转换为事件，一共n^k次事件，我们每扔一次硬币就可以看作有n次操作，m次为硬币朝上，n-m次硬币朝下。
我们设b(n)为抛n次硬币之后，硬币朝上次数为奇数的操作次数；a(n)为抛k次硬币之后，硬币朝上次数为偶数的操作次数。那么有递推式子
b（n）=b(n-1) * (n-m)+ a(n-1) * m;
a(n)=a(n-1) * (n-m)+ b(n-1) * m;
这个构造矩阵就容易多了
ac代码：

#include <cstdio>

#include <iostream>

using namespace std;

typedef long long ll;

const ll mod=1e9+;

struct Martix

{

    ll mp[][];

    int r,c;

};

ll exgcd(ll a,ll b,ll &x,ll &y)// 扩展欧几里得

{

    if(b==)

    {

        x=;

        y=;

        return a;

    }

    ll temp=exgcd(b,a%b,y,x);

    y-=(a/b)*x;

    return temp;

}

ll finv(ll a,ll m)// 求逆元

{

    ll x,y;

    ll g=exgcd(a,m,x,y);

    x=(x%m+m)%m;//

    return x;

}

 long long quickmod(long long a,long long b,long long m)

{

    long long ans = ;

    while(b)//用一个循环从右到左便利b的所有二进制位

    {

        if(b&)//判断此时b[i]的二进制位是否为1

        {

            ans = (ans*a)%m;//乘到结果上，这里a是a^(2^i)%m

            b--;//把该为变0

        }

        b/=;

        a = a*a%m;

    }

    return ans;

}

Martix mul(Martix a,Martix b)

{

    int r=a.r;

    int c=b.c;

    Martix temp;

    temp.r=r;

    temp.c=c;

    for(int i=;i<r;i++)

    {

        for(int j=;j<c;j++)

        {

            temp.mp[i][j]=;

            for(int k=;k<r;k++)

            {

                temp.mp[i][j]=(a.mp[i][k]*b.mp[k][j]+temp.mp[i][j])%mod;

            }

        }

    }

    return temp;

}

ll n,m;

ll pow(Martix a,ll k)

{

    Martix ans;

    ans.r=;

    ans.c=;

    ans.mp[][]=n-m;//

    ans.mp[][]=m;//

    while(k)

    {

        if(k&) ans=mul(a,ans);

        k/=;

        a=mul(a,a);

    }

    return ans.mp[][]%mod;

}

int main()

{

    int t;

    ll k;

    scanf("%d",&t);

    while(t--)

    {

          scanf("%lld %lld %lld",&n,&m,&k);

          ll y=quickmod(n,k,mod);

          Martix a;

          a.r=a.c=;

          a.mp[][]=a.mp[][]=n-m;

          a.mp[][]=a.mp[][]=m;

          ll key=pow(a,k-);

          //cout<<key<<endl;

          ll temp=key*finv(y,mod)%mod;

          cout<<temp<<endl;

    }

    return ;

}

巴特西

2017 ACM-ICPC 亚洲区（西安赛区）网络赛 Coin 矩阵快速幂

Input Format

Output Format

样例输入

样例输出

最新文章

热门文章