华华送奕奕小礼物

https://ac.nowcoder.com/acm/contest/894/B

推公式+矩阵快速幂

1、假设在第  次后剩下  个黑球，那么第  次操作后黑球数  公式如下：

2、有概率  放入黑球，取出的球是黑球的概率为  ，剩余黑球数量的期望是 ，同理推出其他

3、得到递推式 

4、考虑矩阵快速幂，令   ，

code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int len = 2;
const ll mod = 1e9 + 7;
struct node
{
	ll martix[len][len];
	void zero()
	{
		memset(martix, 0, sizeof(martix));
	}
	void one()
	{
		for (int i = 0; i < len; i++)
			for (int j = 0; j < len; j++)
				if (i == j)
					martix[i][j] = 1;
				else
					martix[i][j] = 0;
	}
	void set(ll temp[len][len])
	{
		for (int i = 0; i < len; i++)
			for (int j = 0; j < len; j++)
				martix[i][j] = temp[i][j];
	}
	node operator *(const node& o)
	{
		node ans;
		ans.zero();
		for (int i = 0; i < len; i++)
			for (int j = 0; j < len; j++)
				for (int k = 0; k < len; k++)
					ans.martix[i][k] = (ans.martix[i][k] + martix[i][j] * o.martix[j][k]) % mod;
		return ans;
	}
};
ll power(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
node power(node a, ll b)
{
	node res;
	res.one();
	while (b)
	{
		if (b & 1)
			res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
int main()
{
	ll n, m, k, a, b;
	scanf("%lld%lld%lld%lld%lld", &n, &m, &k, &a, &b);
	ll p = a * power(b, mod - 2) % mod;
	ll q = (n + m) * power(n + m + 1, mod - 2) % mod;
	p = p * q % mod;
	ll pres[len][len] = {
		{n,p},
		{0,0}
	};
	ll t[len][len] = {
		{q,0},
		{1,1}
	};
	node temp;
	temp.set(t);
	node pre;
	pre.set(pres);
	temp = power(temp, k);
	pre = pre * temp;
	printf("%lld\n", pre.martix[0][0]);
}