Tom and matrix
Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=5226
Mean:
题意很简单，略。
analyse:
直接可以用Lucas定理+快速幂水过的，但是我却作死的用了另一种方法。
方法一：Lucas定理+快速幂水过
方法二：首先问题可以转化为求(0,0)，(n,m)这个子矩阵的所有数之和。画个图容易得到一个做法，对于n<=m，答案就是2^0+2^1+...+2^m=2^(m+1)-1，对于n>m，答案由两部分构成，一部分是2^(m+1)-1，另一部分是sigma i:m+1->n f[i][m]，f[i][m]表示第i行前m列的数之和，f数组存在如下关系，f[i][m]=f[i-1][m]*2-C[i-1][m]，f[m][m]=2^m。还有另一种思路：第i列的所有数之和为C(i,i)+C(i+1,i)+...+C(n,i)=C(n+1,i+1)，于是答案就是sigma i:0->min(n,m) C(n+1,i+1)。
Lucas定理：由于题目给定的模是可变的质数，且质数可能很小，那么就不能直接用阶乘和阶乘的逆相乘了，需要用到Lucas定理，公式：C(n,m)%P=C(n/P,m/P)*C(n%P,m%P)，c(n,m)=0(n<m)。当然最终还是要预处理阶乘和阶乘的逆来得到答案。复杂度O(nlogP+nlogn)
Time complexity: O(n)
Source code:
Lucas定理+快速幂
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-05-21-23.28
* 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; const int maxn=;
struct cell
{
int x,y;
bool operator<(cell c) const
{
return x==c.x?(y<c.y):(x<c.x);
}
}p[];
LL mod;
LL Pow(LL a,LL b)
{
LL ret=;
a%=mod;
while(b)
{
if(b&) ret=ret*a%mod;
a=a*a%mod;
b>>=;
}
return ret%mod;
}
namespace lucas
{
LL A[maxn],inv[maxn];
void init()
{
A[]=,A[]=;
inv[]=;inv[]=;
for(int i=;i<maxn;i++)
{A[i]=A[i-]*(LL)i%mod;inv[i]=Pow(A[i],mod-);}
}
LL Lucas(LL a,LL b)
{ if(a<b) return ;
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;
}
}
using namespace lucas; int main()
{
ios_base::sync_with_stdio(false);
cin.tie();
while(cin>>p[].x>>p[].y>>p[].x>>p[].y>>mod)
{
if(p[].y>p[].x&&p[].y>p[].x&&p[].y>p[].x) {printf("0\n");continue;}
init();
sort(p,p+);
if(!(p[].x<=p[].x && p[].y<=p[].y))
{
int x1=p[].x,y1=p[].y,x2=p[].x,y2=p[].y;
p[].x=x1,p[].y=y2,p[].x=x2,p[].y=y1;
}
LL sta=p[].x,en=p[].x,h=p[].y,ans=;
while(h<=p[].y && sta<=en )
{
if(sta<h) sta=h;
ans=(ans+Lucas(en+,h+)-Lucas(sta,h+)+mod)%mod;
h++;
}
printf("%lld\n",ans); }
return ;
}
/* */
方法二：
/*
* 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[];
LL mod;
LL inv[],A[];
inline LL Pow(LL a,LL b)
{
LL ret=;
a%=mod;
while(b)
{
if(b&) ret=ret*a%mod;
a=a*a%mod;
b>>=;
}
return (ret-)%mod;
} void init()
{
A[]=,A[]=;
inv[]=;inv[]=;
for(int i=;i<;i++)
{A[i]=A[i-]*(LL)i%mod;inv[i]=Pow(A[i],mod-);}
}
LL Lucas(LL a,LL b)
{
if(a<b) return ;
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+;
if(b<) return ;
LL a=;
LL ret=;
a%=mod;
while(b)
{
if(b&) ret=ret*a%mod;
a=a*a%mod;
b>>=;
}
return (ret-)%mod;
} inline int calc_Matrix(int x,int y)
{
if(x<||y<) return ;
if(x<=y)
return Pow(x);
else
{
LL sum1=Pow(y);
LL tmp=Pow(y)-Pow(y-);
LL sum2=;
for(int i=y+;i<=x;++i)
{
tmp=tmp*-(int)Lucas((LL)i-,(LL)y);
tmp%=mod;
sum2+=tmp;
sum2%=mod;
}
return (sum1+sum2)%mod;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie();
while(cin>>p[].x>>p[].y>>p[].x>>p[].y>>mod)
{
if(p[].y>p[].x&&p[].y>p[].x&&p[].y>p[].x) {printf("0\n");continue;}
init();
sort(p,p+);
if(!(p[].x<=p[].x && p[].y<=p[].y))
{
int x1=p[].x,y1=p[].y,x2=p[].x,y2=p[].y;
p[].x=x1,p[].y=y2,p[].x=x2,p[].y=y1;
}
cout<<(calc_Matrix(p[].x,p[].y)-calc_Matrix(p[].x-,p[].y)-calc_Matrix(p[].x,p[].y-)+calc_Matrix(p[].x-,p[].y-))%mod<<endl;
}
return ;
}
/* */