Problem Turn the pokers （HDU 4869）
题目大意
有m张牌，全为正面朝上。进行n次操作，每次可以将任意ai张反面，询问n次操作可能的状态数。
解题分析
记正面朝上为1，朝下为0。
若最后有x个1，则对答案的贡献为C（n，x）。所以只需要知道最后可能的1的个数。
假设已经有a个1，某次操作可以将b张牌反面，可以发现操作之后可能的1的个数相差2。
记录每次操作后1的个数所在区间为[l ，r]，即可能取到的个数为l , l+2 , l+4 , ...... , r 。
每次转移分类讨论一下，贪心转移即可。
参考程序
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 using namespace std; 6 7 #define N 100008 8 #define mo 1000000009 9 int a[N]; 10 int pa[N],pb[N]; 11 int n,m; 12 13 void calc(int &l,int &r,int x){ 14 int ll,rr; 15 if (x<l) ll=l-x; 16 if (l<=x && x<=r) ll=(r-x) & 1; 17 if (r<x) ll=x-r; 18 19 if (x<m-r) rr=x+r; 20 if (m-r<=x && x<=m-l) rr=m-((m-l-x) & 1); 21 if (m-l<x) rr=m-(x-(m-l)); 22 l=ll; r=rr; 23 } 24 25 int C(int x,int y){ 26 return 1ll*pa[x]*pb[y] % mo *pb[x-y] % mo; 27 } 28 29 int quick_pow(int x,int y){ 30 int res=1; 31 while (y){ 32 if (y&1) res=1ll*res*x % mo; 33 x=1ll*x*x % mo; 34 y=y >>1; 35 } 36 return res; 37 } 38 39 int main(){ 40 pa[0]=pb[0]=1; 41 for (int i=1;i<N;i++) pa[i]=(1ll*pa[i-1]*i) % mo; 42 for (int i=1;i<N;i++) pb[i]=quick_pow(pa[i],mo-2); 43 while (~scanf("%d %d",&n,&m)){ 44 for (int i=1;i<=n;i++) scanf("%d",&a[i]); 45 int l=0,r=0; 46 for (int i=1;i<=n;i++) calc(l,r,a[i]); 47 48 long long ans=0; 49 for (int i=l;i<=r;i+=2) ans= (ans+C(m,i)) % mo; 50 printf("%I64d ",ans); 51 } 52 }