[C++知识库]arc061 F - Card Game for Three

F - Card Game for Three

显然要出现n张a在m + 1张b、k + 1张c之前，使得Alice获胜，游戏结束。

考虑枚举b和c一共出现i次，以及把这i次插入a中（得在最后1个a之前），之后剩余牌即可任选的方案数，为C(n + i - 1, i) * 3 ^ (m + k - i)

再考虑这i次中b和c分别出现几次，此时限制为b小于等于m次，c小于等于k次。发现这个东西是可以随着i增大O（1）维护的，不妨记这个东西为t，则(i - 1) -> i，t = t * 2 - C(i - 1, m) - C(i - 1, k)

 #include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define ll long long
#define trav(v,x) for(auto v:x)
#define all(x) (x).begin(), (x).end()
#define VI vector<int>
#define VLL vector<ll>
#define pll pair<ll, ll>
#define double long double
//#define int long long
using namespace std;
const int N = 1e6 + 100;
const int inf = 1e9;
//const ll inf = 1e18;
const ll mod = 1e9 + 7;

#ifdef LOCAL
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
	cerr << " " << to_string(H);
	debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

void sol()
{
	int n, m, k;
	cin >> n >> m >> k;
	VLL fac(N + 1);
	fac[0] = 1;
	for(int i = 1; i <= N; i++)
		fac[i] = fac[i - 1] * i % mod;
	VLL ifac(N);
	auto qpow = [&](ll x, ll y = mod - 2)
	{
		ll res = 1;
		while(y)
		{
			if(y & 1)
				res = res * x % mod;
			x = x * x % mod;
			y >>= 1;
		}
		return res;
	};
	ifac[N] = qpow(fac[N]);
	for(int i = N - 1; i >= 0; i--)
		ifac[i] = ifac[i + 1] * (i + 1) % mod;
	auto C = [&](ll x, ll y)
	{
		if(y < 0)
			return 0LL;
		if(x < y)
			return 0LL;
		return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
	};
	VLL pw(N + 1);
	pw[0] = 1;
	for(int i = 1; i <= N; i++)
		pw[i] = pw[i - 1] * 3 % mod;
	ll ans = 0, t;
	for(int i = 0; i <= m + k; i++)
	{
		ll nw = C(n + i - 1, i) * pw[m + k - i] % mod;
		if(i == 0)
		{
			t = 1;
		}
		else
		{
			t = t * 2 % mod;
			if((i - 1) >= m)
				t = (t + mod - C(i - 1, m)) % mod;
			if((i - 1) >= k)
				t = (t + mod - C(i - 1, i - 1 - k)) % mod;
		}
		//cerr << i << ' ' << s << ' ' << t << '\n';
		ans = (ans + nw * t) % mod;
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
//	int tt;
//	cin >> tt;
//	while(tt--)
		sol();
}