题解：官方给出的题解看了半天看懂了一部分。后来看了别人的博客。讲的挺具体可是有的地方还是非常难懂，和朋友讨论了半天最终弄懂了全部的细节。
首先。我们把牌的正反面的情况规定成0，1的情况（0反，1正）。进行m次操作，共翻转s=sum（x0+x1+....+xm-1）次，最后出现1的数目必定和s同奇同偶（s为奇数，1的个数就为奇数，反之为偶数）----每翻转一张牌（把1翻转成0，0翻转成1）。1的个数都发生奇偶变化。開始时没翻转。也就是0次翻转，1的个数为偶数。翻转1次变奇数。再翻转一次变偶数.....依次类推，以上得证。
那么这样我们就能找出最后1的个数的最小数目l和最大数目r（l，r与s同奇偶），中间过程中我们把某两次从0翻转成1的情况拿出来。翻转同一张牌（相当于相互抵销）。那我们最后1的个数就会多2或少2。这样我们最后1的个数就是l。l+2，.....。r-2，r的等差数列，然后用求出c（m，i）的和就能够了。所以主要任务就是求出l和r。代码中有凝视具体解释。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef __int64 LL; static const int mod = 1000000009; LL quick_mod(LL a,LL b) { LL t=1; while(b) { if(b&1) t=t*a%mod; b/=2; a=a*a%mod; } return t; } int main() { LL m,n,x; while(cin>>m>>n) { LL l=0,r=0,p=0,q=0; //l用来记录前一状态1的最小数，r为最大数 //p用来记录当前状态1的最小数，q为最大数 for(LL i=0;i<m;i++) { cin>>x; //求取最少1的数目，有1翻1 if(l-x>=0) p=l-x; //1）当前状态1的最少数目为l，挑选x张牌翻转， // 当l>=x，也就是说我能把当中随意x张1翻转成0 else if(r-x>=0) p=(r-x)%2; //2）x>l&&x<=r,因为当前状态1的个数最大为r，最小为l， //其次我能够通过前面的情况构造[l,r]中与l同奇偶数 //所以我仅仅要构造出与x离得近期的那个就能够使得p仅仅需i小 else p=x-r; //3)x大于当前状态1的最大数目，也就是我除了把这r个1翻转成0 //还须要把x-r个0翻转成1，最小数目为x-r //求取最多1的数目。有0翻0 if(r+x<=n) q=r+x; //与上面类似，不再赘述 else if(l+x<=n) q=n-((n-l)%2!=x%2); else q=2*n-(l+x); l=p,r=q; } LL c[100010],ans=0; //使用c数组记录c(m,i)%mod c[0]=1; if(l==0) ans+=1; for(LL i=1;i<=r;i++) { if(n-i<i) c[i]=c[n-i]; else c[i]=c[i-1]*(n-i+1)%mod*quick_mod(i,mod-2)%mod; //这里使用了c(m,i)=c(m,i-1)*(m-i+1)/i的求法 //因为过程中须要取余。所以不能直接用公式计算 //当除以一个数k同一时候对p取余时，能够把除法转化成乘以这个数k对于p的逆元来计算 //k对于p的逆元的求法就是k*x≡1(mod)p,全部满足上述条件的x都是一个逆元 //因为p是素数，依据费马小定理k^(p-1)≡1(mod)p //这里进行一下分解k*k^(p-2)≡1(mod)p，可看出k^(p-2)是k对于p的一个逆元 if((l%2==i%2)&&i>=l) ans=(ans+c[i])%mod; } cout<<ans<<endl; } return 0; }版权声明：本文博客原创文章。博客，未经同意，不得转载。
转载于:https://www.cnblogs.com/bhlsheji/p/4686266.html
相关资源：数据结构—成绩单生成器