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

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是大素数。除法操作可用逆元求解取代。

#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;
}