Turn the pokers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1265 Accepted Submission(s): 465
Problem Description
During summer vacation,Alice stay at home for a long time, with nothing to do. She went out and bought m pokers, tending to play poker. But she hated the traditional gameplay. She wants to change. She puts these pokers face down, she decided to flip poker n
times, and each time she can flip Xi pokers. She wanted to know how many the results does she get. Can you help her solve this problem?
times, and each time she can flip Xi pokers. She wanted to know how many the results does she get. Can you help her solve this problem?
pid=4869">http://acm.hdu.edu.cn/showproblem.php?pid=4869
思路:可惜了,比赛中没有想出来,一比赛出来就想到了。
首先考虑两次翻转。翻转a个和b个,最好还是设a>b。如今考虑翻转后正面朝上的个数(如果一開始都是背面朝上,以下用0表示背面朝上,1表示正面朝上)。翻转后。1的个数最大可能为a+b,最小为a-b。进一步观察可发现经过两次翻转。1的个数可取的值为最小值为a-b,最大值为a+b,且间隔为2的一个区间,也就是a-b,a-b+2,a-b+4......a+b-2,a+b。那么如今如果再加一个数C,同理可得到1的个数会是一个区间,那么我们仅仅要维护这个区间就可以。
注意会有这种情况,比方a+b超过n或a-b小于0,这个时候就要讨论算出新的区间。这个细致分情况讨论就可以。
最后算出1的个数的区间[L,R]后。最后的答案就为C(n,L)+C(n,L+2)+C(n,L+4)+......C(n,R),最后要取模1e9+7。(C(n,m)为n个数中取m个的组合数)由于这里的n比較大,所以不能直接按公式C[n][m]=C[n-1][m]+C[n-1][m-1]来做。由于C(n,m)=n!/(m!*(n-m)!),那么预处理出n!和n!关于1e9+7的逆元,再依据公式就可以得到答案。
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#define ll long long
#define maxn 100010
#define mod 1000000009
using namespace std;
ll pow(ll x,ll y)
{
if(y==0)
return 1;
ll tmp=pow(x,y/2);
tmp=(tmp*tmp)%mod;
if(y&1)
tmp=tmp*x%mod;
return tmp;
}
ll c[maxn],b[maxn];
void init()
{
c[0]=1;
for(int i=1;i<=100000;i++)
c[i]=(c[i-1]*i)%mod;
for(int i=0;i<=100000;i++)
b[i]=pow(c[i],mod-2);
}
ll getC(int n,int m)
{
if(m==0||m==n)
return 1;
ll tmp=c[n]*b[m]%mod*b[n-m]%mod;
return tmp;
}
int main()
{
freopen("dd.txt","r",stdin);
init();
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int x;
int l=0,r=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
int rr=r;
if(r+x<=m)
r+=x;
else
{
if(l+x<=m)
{
if((m-l-x)%2)
r=m-1;
else
r=m;
}
else
{
r=m-(l+x-m);
}
}
if(l-x>=0)
l-=x;
else
{
if(rr>=x)
{
if((rr-x)%2)
l=1;
else
l=0;
}
else
l=x-rr;
}
}
ll ans=0;
for(int i=l;i<=r;i+=2)
{
ans=(ans+getC(m,i))%mod;
}
printf("%I64d\n",ans);
}
return 0;
}