首页 > 代码库 > [hdu 4869](14年多校I题)Turn the pokers 找规律+拓欧逆元

[hdu 4869](14年多校I题)Turn the pokers 找规律+拓欧逆元

2024-07-13 14:21:33   223人阅读

Turn the pokers


Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 316    Accepted Submission(s): 101




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?
 


Input
The input consists of multiple test cases. 
Each test case begins with a line containing two non-negative integers n and m(0<n,m<=100000). 
The next line contains n integers Xi(0<=Xi<=m).
 


Output
Output the required answer modulo 1000000009 for each test case, one per line.
 


Sample Input


3 4
3 2 3
3 3
3 2 3
 


Sample Output
8
3


Hint
For the second example:
0 express face down,1 express face up
Initial state 000
The first result:000->111->001->110
The second result:000->111->100->011
The third result:000->111->010->101

So, there are three kinds of results(110,011,101)


题目大意

给定M张牌，可以翻转N次，每次可以翻转恰好Xi张牌，刚开始牌面全部朝下，问经过N次翻转之后可能产生的扑克序列数（如样例hint）。

解题思路

现场还是没出……想到dp的思路但复杂度高达N^2.

可以观察到，我们最后正面朝上的牌的数量奇偶总是一定的（如1，3，5），因为不同奇偶情况就需要至少多翻一次，但翻动的次数已经固定不能更改。


考虑一次翻转，最多X1张牌正面朝上了，最少也是X1张。

如果第二次只翻转1张，再设1<X1<m 则最多会有X1+1张牌正面朝上，最少会有X1-1张牌正面朝上。


现在假设我们已经翻好k-1次

最多a张正面朝上，最少b张正面朝上

如果b>=Xk 则翻转后最少有b-Xk张正面朝上（其余的情况可以一次翻一张正面的，一张反面的，情况保持不变）。

否则，如果a>Xk，这时最少会有0张或1张正面朝上（根据a和Xk的奇偶性判断），

再否则，最少会有Ak-a张正面朝上（先把正面朝上的全部翻转，剩下的再翻便是最少张数）


关于最大值的讨论同理


最后关于组合数的计算，由于m固定不变，就可以根据组合数公式C(m,n)=C(m-1,n)*(n-m+1)/m 线性求解，由于1e9+9是大素数，除法操作可用逆元求解代替。

<span style="font-size:14px;">#include <cstdio>
#define LL long long
int n,m;
LL mod=1000000009;
LL a[100005];
void egcd(LL a,LL b,LL &x,LL &y)
{
  if (b==0)
  {
    x=1;y=0;
    return ;
  }
  egcd(b,a%b,x,y);
  LL t=x;
  x=y,y=t-a/b*y;
  return;
}
LL cal(LL x,LL y)
{
  LL cur=1,tmp=0,t=0;
  while(t<=y)
  {
    if (t>=x&&t<=y)
    if ((t-x)%2==0) tmp=(tmp+cur)%mod;
    t++;
    cur=cur*(m-t+1)%mod;
    LL t1,t2;
    egcd(t,mod,t1,t2);
    t1=(t1+mod)%mod;
    cur=cur*t1%mod;
  }
  return tmp;
}
int main()
{
  while (~scanf("%d%d",&n,&m)){
  LL upper,lower,plower,pupper;
  for (int i=1;i<=n;i++)
    scanf("%I64d",&a[i]);
  upper=lower=pupper=plower=0;
  for (int i=1;i<=n;i++)
  {
    if (plower>=a[i]) lower-=a[i];
    else if (pupper>=a[i]) lower=0+((pupper+a[i])%2==1);
    else lower=a[i]-pupper;
    if (pupper+a[i]<=m) upper+=a[i];
    else if (plower+a[i]<=m) upper=m-((plower+a[i])%2==1);
    else {upper=m-(plower+a[i]-m);}
    plower=lower;//plower代表上一步的最小值
    pupper=upper;//pupper代表上一步的最大值
  }
    printf("%I64d\n",cal(lower,upper));
  }
  return 0;
}</span>




[hdu 4869](14年多校I题)Turn the pokers 找规律+拓欧逆元


联系
我们