学步园

思路：

根据观察，发现，最后正面的张数为一些间隔为2的连续的一些数。此题分为两部分，1 求解翻之后正面张数的范围，2 组合数求解。

1，求解范围时只关注最大正面张数和最小正面张数，具体变换关系可以自行推敲。

2，组合数时，因为数据量大且取模，所以要避免正常的除法求解的公式，这里线性求解，除法处理上改为乘法 (a/b) %M=a*(b^(M-2))%M

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const long long M=1e9+9;
long long c[111111];
long long quickpow(long long m,long long n,int k)
{
    long long b = 1;
    while (n > 0)
    {
        if (n & 1)
            b = (b*m)%k;
        n = n >> 1 ;
        m = (m*m)%k;
    }
    return b%k;
}
int m,n,x;
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int mi=0,ma=0;
        int a,b;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&x);
            if(mi-x>=0)a=mi-x;
            else if(ma-x>=0)
            {
                if(mi%2==x%2)a=0;
                else a=1;
            }
            else a=x-ma;
            if(ma+x<=m)b=ma+x;
            else if(mi+x<=m)
            {
                if((mi+x)%2==m%2)b=m;
                else b=m-1;
            }
            else b=m-(x-(m-mi));
            mi=a;
            ma=b;
        }
        long long mu=m,zi=1,xx,yy;
        c[0]=1;
        for(int i=1;i<=m;i++)
        {
            if(m-i<i)c[i]=c[m-i];
            else
            {
                c[i]=(c[i-1]*(m-i+1))%M*quickpow((long long)i,M-2,M)%M;
            }
        }
        long long ans=0;
        for(int i=mi;i<=ma;i+=2)
        {
            ans+=c[i];
            ans%=M;
        }
        cout<<ans<<endl;
    }
    return 0;
}