All in

NC17668. All in

描述

Niuniu likes gambling.

Team A and B will play 2n-1 matches.

Niuniu wants to bet 2^2n-1 that team A wins the entire series.

In other words, if A wins n or more matches, Niuniu will gain 2^{2n - 1}

If A loses(B wins) n or more matches, Niuniu will lose 2^{2n - 1}(gain -2^{2n - 1})

However, the banker does not allow such a bet. Niuniu can only bet on individual matches.

The winning percentage of both teams is 0.5. All matches are independent of each other.

Niuniu can bet on the (i+1)-th match after seeing the results of the first i games.

Your program need read n and output the bet on the first match.

Then read the result of the first match, output the bet on the second match.

Then read the result of the second match, output the bet on the third match.

....

Finally, read the result of the (……)-th match, and team A wins or loses the entire series, the program ends.

The answer can be uniquely determined, and this is not a interactive problem.

As the result might be very large, you should output the result mod 1000000007.

输入描述

The first line contains an integer, which is n.
The second line contains the results of contests, which are 0s and 1s.
0 means team A wins, and 1 means team A loses(team B wins)
It is guaranteed this is a legal process.

Once the number of 0 or 1 reaches n, there will be no more input.

1 <= n <= 100000

输出描述

You should output the bet for each contest in a new line.
The number of output is the same as the second line of input.

示例1

输入:

2
0 1 1

输出:

4
4
8

说明:

In fact, for n = 2, the bets are always 4 4 8, no matter what the outcome of the matches.

If team A (or B) wins the first two matches, Niuniu will gain 4 + 4 = 8 (or lose 4 + 4 = 8).

If team A and B both win one of the first two matches, Niuniu gains 4 - 4 = 0, and will bet 8 on the third match.

In all situations, Niuniu will gain 8 if team A wins the entire series, and will lose 8 if team A loses the entire series.

示例2

输入:

3
1 1 0 0 1

输出:

说明:

The sum of all bets (with sign) is -2^2n-1or 2^2n-1

(-12) + (-12) + (8) + (16) + (-32) = -32 = -2⁵

示例3

输入:

3
0 1 0 0

输出:

说明:

(12) + (-12) + (16) + (16) = 32 = 2⁵

You can make the third bet, based on the first two result.

示例4

输入:

2
1 1

输出:

4
4

说明:

Team A wins the first two matches. There won't be a third match.

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 96ms, 内存消耗: 7764K, 提交时间: 2018-08-16 16:38:33

#include<bits/stdc++.h>
#define maxn 234035

using namespace std;
typedef long long ll;
const ll M=1000000007;
ll n,m,nf[maxn],f[maxn],k,p2[maxn],r,x,y,o;
ll pow_(ll x,ll y){
    ll rt=1;
    while (y){
        if (y&1) rt=rt*x%M;
        x=x*x%M;
        y>>=1;
    }
    return rt;
}
ll C(ll x,ll y){
    return f[x+y]*nf[x]%M*nf[y]%M;
}
int main(){
    f[0]=nf[0]=p2[0]=1;
    for (int i=1;i<maxn;i++) f[i]=f[i-1]*i%M;
    for (int i=1;i<maxn;i++) nf[i]=nf[i-1]*pow_(i,M-2)%M;
    for (int i=1;i<maxn;i++) p2[i]=p2[i-1]*2%M;
    cin >> n;
    r=1; x=n-1; y=n-1; n++;
    while (true){
        printf("%lld\n",C(x,y)*p2[r]%M);
        scanf("%lld",&o);
        if (o) x--; else y--; r++;
        if (x<0||y<0) return 0;
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 52ms, 内存消耗: 3936K, 提交时间: 2020-04-03 15:53:02

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
ll a,b,ans;
ll inv[2*N];
int n,x;
ll cal(ll x,ll y)
{
	ll ret=1;
	for(int i=1;i<=y;++i)
	ret=ret*(x-i+1)%mod*inv[i]%mod;
	return ret;
 } 
int main()
{
	scanf("%d",&n);
	inv[1]=1;
	for(int i=2;i<2*n;++i)
	inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	ans=cal(2*n-2,n-1)*2%mod;
	a=b=0;
	while(a<n&&b<n)
	{
		printf("%lld\n",ans);
		scanf("%d\n",&x);
		ans=ans*inv[2*n-a-b-2]%mod*2%mod;
		if(!x) ++a,ans=ans*(n-a)%mod;
		else ++b,ans=ans*(n-b)%mod;
	}
}