HDU：Turn the pokers

HDU：Turn the pokers

题目链接：https://cn.vjudge.net/contest/163787#overview

题目大意：现有$m$张正面朝下的扑克牌，接下来有$n$次操作，每次可以将$X_i$张扑克翻转，问最终扑克的朝向方案有多少种.

贪心

易得，如果结果有$k$张扑克为正面朝上，那么答案将所有$k$张正面朝上的方案，从而只需计算最终可能有哪些$k$存在.

根据翻转的特点（翻转后所有的$k$值奇偶性相同）有，每次操作后可能存在的$k$值为公差为$2$的等差数列，

故每次操作只需维护最小$k$值$l$和最大$k$值$r$即可.

不难得到：

$l_{i+1}=min{|X_i-a|:l_i leqslant a leqslant r_i}$
$r_{i+1}=m-min{|X_i-(m-a)|:l_i leqslant a leqslant r_i}$

最后求得$ans=sum_{k=l}^{k=r}(_k^m)$.

/*坑点：p=1e9+9*/

代码如下：

 1 #include <cstdio>
 2 #define N 100000
 3 using namespace std;
 4 typedef long long ll;
 5 const ll p=1e9+9;
 6 ll fac[N+5],inv_fac[N+5],n,m;
 7 ll powmod(ll a,ll n){
 8     ll r=1;
 9     while(n){
10         if(n&1)r=(r*a)%p;
11         a=(a*a)%p;
12         n>>=1;
13     }
14     return r;
15 }
16 ll C(ll m,ll n){
17     return fac[n]*inv_fac[m]%p*inv_fac[n-m]%p;
18 }
19 void init(){
20     fac[0]=1;
21     for(int i=1;i<=N;++i)
22         fac[i]=(fac[i-1]*i)%p;
23     inv_fac[N]=powmod(fac[N],p-2);
24     for(int i=N-1;i>=0;--i)
25         inv_fac[i]=(inv_fac[i+1]*(i+1))%p;
26 }
27 ll fmin(ll l,ll r,ll x){
28     if(l<=x&&x<=r)return (x-l)%2;
29     else if(x<l)return l-x;
30     else return x-r;
31 }
32 ll fmax(ll l,ll r,ll x){
33     return m-fmin(m-r,m-l,x);
34 }
35 int main(void){
36     init();
37     while(~scanf("%lld%lld",&n,&m)){
38         ll l=0,r=0,x,ans=0;
39         while(n--){
40             scanf("%lld",&x);
41             ll tl=fmin(l,r,x);
42             ll tr=fmax(l,r,x);
43             l=tl;r=tr;
44         }
45         for(ll i=l;i<=r;i+=2)
46             ans=(ans+C(i,m))%p;
47         printf("%lld
",ans);
48     }
49 }