牛客小白月赛16 I 石头剪刀布 期望

	#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]);



	}