[C++知识库]Educational Codeforces Round 136 (Rated for Div. 2) C. Card Game

原题链接：Problem - 1739C - Codeforces

题意：n?张卡，Alice?和Bob?轮流出牌，对方应牌，不能应牌的一方失败，应牌要求是比对方出的大。

思路：我们考虑Alice必胜的情况：

1.若AIice拿到了n，剩下的牌无论Alice怎么拿Alice都必赢，因为Alice可以在第一轮就出n，Bob没有比n更大的牌可以出，就输掉了。组合数为C[n-1][(n/2)-1]。

2.若Alice没有拿到n，而是拿到了n-1，Alice则必须将n-1用来逼出Bob的n，否则她就会输掉。而将用n-1逼出了n，相当于牌堆里少了两张牌，也就是回到了总牌数为n-2的情况，唯一不同的是，这次是Bob先手，而总牌数为n-2时是Alice先手，相当于总牌数为n-2时的Bob变成了总牌数为n时的Alice，而总牌数为n-2时的Alice变成了总牌数为n时的Bob，所以这时总牌数为n时Alice获胜的情况数就是总牌数为n-2时的Bob获胜的情况数，所以当Alice只拿到了n-1的情况数即为b[n-2]。

因此，Alice获胜的总情况数为C[n-1][(n/2)-1]+b[n-2]。

而平局的情况数我们可以这样证明：

假设Alice得到了牌n，那么Alice就赢了。因为他可以立即出牌。所以，如果要平局，Bob必须得到牌n。

假设Bob收到一张牌n?1，那么Bob就赢了。因为通过第一步证明我们得知他还一张牌n，他可以用n来应对Alice第一步的任意一张牌，然后通过出n?1来赢得游戏。因此，如果游戏的结果是平局，Alice必须得到牌n?1。

假设Bob收到一张牌n?2，那么Bob就赢了。因为他也有牌n:如果Alice出牌n?1,Bob以n回应，然后出牌n?2;如果Alice出另一张牌，Bob的回应是n?2，下一回合出n。因此，要想平局，Alice必须得到牌n?2。

以此类推。

由此可以得出平局的局面只有一种，而Alice赢的局面有C[n-1][(n/2)-1]+b[n-2]种，剩下的局面即为Bob赢的局面了，即为c[n][n/2]（总组合数）-a[n]（Alice赢）-1（平局）。

void init() {
	a[2] = 1, b[2] = 0;
	for (int i = 0; i <= 60; i++) {
		c[i][0] = c[i][i] = 1;
		for (int j = 1; j < i; j++) {
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
		}
	}
	for (int i = 4; i <= 60; i += 2) {
		a[i] = (c[i - 1][(i / 2) - 1] + b[i - 2]) % mod;
		b[i] = (c[i][i / 2] - a[i] - 1 + mod) % mod;
	}
}
void solve() {
	int n;
	cin >> n;
	cout << a[n] << " " << b[n] << " " << 1 << endl;
}