链接：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]);





	}