组合数（卢卡斯定理）+快速幂 --- HDU 5226 汤姆和矩阵

/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-05-21-02.58 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #define LL long long #define ULL unsigned long long using namespace std; struct cell { int x,y; bool operator<(cell c) const { return x==c.x?(y<c.y):(x<c.x); } }p[2]; LL mod; LL inv[101000],A[101000]; inline LL Pow(LL a,LL b) { LL ret=1; a%=mod; while(b) { if(b&1) ret=ret*a%mod; a=a*a%mod; b>>=1; } return (ret-1)%mod; } void init() { A[0]=1,A[1]=1; inv[1]=1;inv[0]=1; for(int i=2;i<101000;i++) {A[i]=A[i-1]*(LL)i%mod;inv[i]=Pow(A[i],mod-2);} } LL Lucas(LL a,LL b) { if(a<b) return 0; if(a<mod&&b<mod) return (A[a]*inv[b]%mod)*inv[a-b]%mod; return Lucas(a/mod,b/mod)*Lucas(a%mod,b%mod)%mod; } inline LL Pow(LL b) { b=b+1; if(b<0) return 0; LL a=2; LL ret=1; a%=mod; while(b) { if(b&1) ret=ret*a%mod; a=a*a%mod; b>>=1; } return (ret-1)%mod; } inline int calc_Matrix(int x,int y) { if(x<0||y<0) return 0; if(x<=y) return Pow(x); else { LL sum1=Pow(y); LL tmp=Pow(y)-Pow(y-1); LL sum2=0; for(int i=y+1;i<=x;++i) { tmp=tmp*2-(int)Lucas((LL)i-1,(LL)y); tmp%=mod; sum2+=tmp; sum2%=mod; } return (sum1+sum2)%mod; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); while(cin>>p[0].x>>p[0].y>>p[1].x>>p[1].y>>mod) { if(p[0].y>p[0].x&&p[1].y>p[1].x&&p[0].y>p[1].x) {printf("0\n");continue;} init(); sort(p,p+2); if(!(p[0].x<=p[1].x && p[0].y<=p[1].y)) { int x1=p[0].x,y1=p[0].y,x2=p[1].x,y2=p[1].y; p[0].x=x1,p[0].y=y2,p[1].x=x2,p[1].y=y1; } cout<<(calc_Matrix(p[1].x,p[1].y)-calc_Matrix(p[0].x-1,p[1].y)-calc_Matrix(p[1].x,p[0].y-1)+calc_Matrix(p[0].x-1,p[0].y-1))%mod<<endl; } return 0; } /* */