HDU 5226 Tom and matrix（组合数学+Lucas定理）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5226

题意：给一个矩阵a，a[i][j] = C（i，j）(i>=j) or 0(i < j)，求(x1，y1)，(x2，y2)这个子矩阵里面的所有数的和。

思路：首先可以推导出一个公式C（n，i）+C（n + 1，i）+...+C（m，i） = C（m + 1，i + 1）

知道了这个公式，就可以将子矩阵里每行（或每列）的和值表示成组合数的差值，现在的关键是求出C（n，m）（mod p）.

由于n和m可能很大，p很小，不能直接求，要借助Lucas定理。关于Lucas定理，可参考：http://www.cnblogs.com/zxndgv/archive/2011/09/17/2179591.html。

code：

 #include <cstdio>

 typedef __int64 LL;

 const int MAXN = ;

 int p;

 LL fac[MAXN];

 // 得到阶乘  fac[i] = i! % p

 void GetFact()

 {

     fac[] = ;

     for (LL i = ; i < MAXN; ++i)

         fac[i] = fac[i - ] * i % p;

 }

 // 快速模幂 a^b % p

 LL Pow(LL a, LL b)

 {

     LL temp = a % p;

     LL ret = ;

     while (b)

     {

         if (b & ) ret = ret * temp % p;

         temp = temp * temp % p;

         b >>= ;

     }

     return ret;

 }

 /*

 欧拉定理求逆元

 (a / b) (mod p) = (a * x) (mod p) x表示b的逆元 并且 b * x = 1 (mod p) 只有b和p互质才存在逆元

 b * x = 1 (mod p) x是b关于p的逆元

 b^phi(p) = 1 (mod p)

 b * b^(phi(p) - 1) (mod p) = b * x (mod p)

 x = b^(phi(p) - 1) = b^(p - 2)

 (a / b) (mod p) = (a * x) (mod p) = (a * b^(p - 2)) (mod p)

 经过上面的推导，得出：

 (a / b) (mod p) = (a * b^(p - 2)) (mod p) (b 和 p互质)

 */

 LL Cal(LL n, LL m)

 {

     if (m > n) return ;

     return fac[n] * Pow(fac[m] * fac[n - m], p - ) % p;

 }

 LL Lucas(LL n, LL m)

 {

     if (m == ) return ;

     return Cal(n % p, m % p) * Lucas(n / p, m / p) % p;

 }

 int main()

 {

     int x1, y1, x2, y2;

     while (scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &p) == )

     {

         if (x2 < y1)    // 预判 子矩阵全部0值区域

         {

             printf("0\n");

             continue;

         }

         if (x2 == y1)   // 预判 子矩阵只有右上角值为1，其余为0

         {

             printf("1\n");

             continue;

         }

         GetFact();

         if (x1 < y1) x1 = y1;

         if (y2 > x2) y2 = x2;

         LL ans = ;

         for (int i = y1; i <= y2; ++i)

         {

             if (i > x1)

                 ans = (ans + Lucas(x2 + , i + )) % p;

             else

                 ans = (ans + Lucas(x2 + , i + ) - Lucas(x1 + , i + ) + Lucas(x1, i)) % p;

         }

         printf("%I64d\n", ans);

     }

     return ;

 }