M(8, 7) * M(8, 3) = M(8, 4) + M(8, 6)

可以看到，实际上的答案是M(8, 4) * M(8, 6) * M(8, 3) = M(8, 0) + M(8, 2) + M(8, 4) + M(8, 6) + M(8, 8)

换句话说，如果我们记录上下界，岂不是很方便？这样就不会一层一层的展开了。

所以问题就被我们抽象成：计算每一层的区间，同时考虑奇偶性。

计算区间并且记录奇偶性

每一次我都对上一次的答案区间进行更新。其实更准确的说实际上是在检查是否需要放大区间。特别判断不在这个区间的x（相当于上文中的M(n, k)中的k）的情况，并且正确的赋值就行，也就是low = 0, high = n。其余的就判断与当前的区间的边界的距离，一个取小值，一个取大值。

当然不能忘记处理奇偶性。奇偶性和异或运算很类似，所以我是用异或搞的。

最后因为是一个公差为2的序列，但是我们只记录了区间和奇偶性。所以应当根据奇偶性去判断答案。

总体的时间复杂度就是O(N){计算区间} - O(N){计算答案}。

组合数的计算

组合数计算公式很简单。C(n, m) = n! / (m! * (n - m)!)

模运算中，除法a / b，等价于a * b^-1，也就是乘上它的逆。所以我们在预处理时计算出逆元的阶乘。

逆元的定义是，满足a * b % p = 1的b，称为a的逆元，有时记做b = inv(a)。计算方法很简单。扩展欧几里得还记得不？ax + by = gcd(a, b)。因为相邻的两个数必然互素，那么就可以写成ax + by = 1。这个不定方程可以和一元线性同余方程互相转化。所以通过扩展欧几里得可以很快的求得逆元。当然也可以直接通过递推的解法来进行计算。

逆元计算好之后，就是查询结果了，这个就是注意每次乘法都要取模就好。

代码示例

ing/******************************************************************************
*       COPYRIGHT NOTICE
*       Copyright (c) 2014 All rights reserved
*       ----Stay Hungry Stay Foolish----
*
*       @author       : Shen
*       @name         : HDU 4869 Turn the pokers
*       @file         : G:\My Source Code\【ACM】比赛\0722 - MUTC[1]\I.cpp
*       @date         : 2014/07/22 13:52
*       @algorithm    : 群论，数论，组合
******************************************************************************/

#include 
   
    
#include 
    
      #include 
     
       using namespace std; template
      
       inline bool updateMin(T& a, T b){ return a > b ? a = b, 1: 0; } template
       
        inline bool updateMax(T& a, T b){ return a < b ? a = b, 1: 0; } typedef long long int64; typedef pair
        
          range; // 答案的范围 // first -> LowerBound, second -> UpperBound const int MaxM = 100005; const int64 MOD = 1000000009; int64 inv[MaxM]; // 逆元，a * inv(a) % p = 1 int64 fac[MaxM]; // 阶乘，1 * 2 * 3 * ... int64 rfc[MaxM]; // 逆元阶乘，inv(1) * inv(2) * inv(3) * ... int n, m; int x[MaxM]; void init() { inv[0] = inv[1] = 1; fac[0] = fac[1] = 1; rfc[0] = rfc[1] = 1; for (int i = 2; i < MaxM; i++) { inv[i] = ((MOD - MOD / i) * inv[MOD % i]) % MOD; fac[i] = (fac[i - 1] * i) % MOD; rfc[i] = (rfc[i - 1] * inv[i]) % MOD; } } inline int64 c(int64 n, int64 k) { return (fac[n] * rfc[k] % MOD) * rfc[n - k] % MOD; } inline bool cmp(int a, int b) { return a > b; } range update(int x, range& cur, bool& isOdd) { int low = 0, high = 0; int curl = cur.first, curh = cur.second; // update IsOdd) isOdd ^= (x % 2 == 1); // update Lower Bound if (curl <= x && x <= curh) low = 0; else low = min(abs(curl - x), abs(curh - x)); // update Upper Bound x = n - x; if (curl <= x && x <= curh) high = n; else high = max(n - abs(curl - x), n - abs(curh - x)); return make_pair(low, high); } void solve() { for (int i = 0; i < m; i++) scanf("%d", &x[i]); range res = make_pair(0, 1); bool isOdd = 0; for (int i = 0; i < m; i++) res = update(x[i], res, isOdd); int64 ans = 0; for (int i = res.first; i <= res.second; i++) if ((i % 2 == 1) == isOdd) ans = (ans + c(n, i)) % MOD; cout << ans << endl; } int main() { init(); while (~scanf("%d%d", &m, &n)) solve(); return 0; }