?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=100010; 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 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%mod; } namespace lucas {LL A[maxn],inv[maxn];void init(){A[0]=1,A[1]=1;inv[1]=1;inv[0]=1;for(int i=2;i<maxn;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;} } using namespace lucas;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;}LL sta=p[0].x,en=p[1].x,h=p[0].y,ans=0;while(h<=p[1].y && sta<=en ){if(sta<h) sta=h;ans=(ans+Lucas(en+1,h+1)-Lucas(sta,h+1)+mod)%mod;h++;}printf("%lld\n",ans);}return 0; } /**/ View Code

方法二：

/* * 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; } /**/ View Code

?

總結

以上是生活随笔為你收集整理的组合数(Lucas定理) + 快速幂 --- HDU 5226 Tom and matrix的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。