链接:https://ac.nowcoder.com/acm/contest/949/I
来源:牛客网
 
石头剪刀布
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld
题目描述
小阳和小石玩石头剪刀布的游戏,他们在地上画了 n 个长度为 1 的格子。
小阳一开始在 1 号格子,如果小阳赢了,那么他就能往前走 1 格(若在 n 号格子,则不往前走)。如果输了,就倒退 1 格(若在 1 号格子,则不往后走),平局原地不动。
小阳已经知道了他石头剪刀布赢的概率是 aa,平的概率是 bb,显然输的概率是 1−a−b1−a−b。
求小阳走到 n 号格子期望进行多少局石头剪刀布。
答案对 109+7109+7 取模。
输入描述:
第一行输入三个正整数 n,a,b,表示格子个数,小阳石头剪刀布赢的概率和平的概率。(概率已对 109+7109+7 取模)
输出描述:
共一行,输出答案。
示例1
输入
复制
50 200000002 400000003
输出
复制
630223353
备注:
1≤n≤100,1<a,b<109+71≤n≤100,1<a,b<109+7
代表从1走到  i  的期望步数
第一个式子

从  2  到n-1个式子

 
注意最后一个式子
 

解模线性方程组
高斯消元即可
当然,矩阵较为稀疏,可以采用更优秀的手解方程方法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=105;
ll a[M][M],ans[M],Id[M];
ll mod=1e9+7;
ll pa,b,n;
ll m;
 
//a[1~n][1~m]代表每个方程每个未知数的系数,a[1~n][0]代表这个方程的值
//ans[1~m]代表每个未知数的解
//Id[1~n]代表每个方程解出的是哪一个未知数
long long qpow(long long a,long long n)
{
    long long ans=1;
    long long base=a;
    while(n)
    {
        if(n&1)
            ans=ans*base%mod;
        base=base*base%mod;
        n>>=1;
    }
    return ans;
}
void solve()
{
    m=n;
    a[1][1]=1;
    a[1][0]=0;
 
    for(int i=2; i<n; i++)
    {
        a[i][i+1]=(1-pa-b+2*mod)%mod;
        a[i][i]=(b-1+mod)%mod;
        a[i][i-1]=pa;
        a[i][0]=mod-1;
    }
    //a[]
    a[n][n]=1;
    a[n][n-1]=mod-1;
    a[n][0]=qpow(pa,mod-2);
    //a[n][n]+=(1-pa-b+2*mod)%mod;
    //a[n]
    memset(Id,-1,sizeof(Id));
    for(int i=1,id=1; i<=n; i++)
    {
        bool f=0;
        while(!f&&id<=m)
        {
            for(int j=i; j<=n; j++)
                if(a[j][id])
                {
                    f=1;
                    break;
                }
            if(f)
            {
                for(int j=i; j<=n; j++)
                    if(a[j][id]) //找到第一个第id个未知数系数不为0的方程
                    {
                        for(int k=0; k<=m; k++)swap(a[i][k],a[j][k]);
                        break;
                    }
                for(int j=i+1; j<=n; j++)
                    if(a[j][id])for(int k=0,tmp=a[j][id]; k<=m; k++)
                            a[j][k]=(a[i][id]*a[j][k]%mod-tmp*a[i][k]%mod+mod)%mod;//消元,构造倒三角
                Id[i]=id;
            }
            id++;//该未知数不存在,无视之,但当前方程还存在,应用其去解下一个未知数
        }
    }
    for(int i=n; i>=1; i--)
    {
        if(Id[i]==-1)continue;
        ans[Id[i]]=a[i][0]*qpow(a[i][Id[i]],mod-2)%mod;//计算解
        for(int j=i-1; j>=1; j--)
            a[j][0]=(a[j][0]-ans[Id[i]]*a[j][Id[i]]%mod+mod)%mod;
    }
}
int main()
{
    cin>>n>>pa>>b;
    solve();
    printf("%lld\n",ans[n]);
}