POJ 3233 二分二分矩阵
/* 由于对二分的不熟练，这道题不知坑了多久... 这道题两次二分，相当经典。首先我们知道，A^i可以二分求出。然后我们需要对整个题目的数据规模k进行二分。 比如，当k=6时，有： A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3) 应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。*/#include<iostream>#include<cstdio>#include<cstring>#include<fstream>#include<cmath>using namespace std;struct Matrix{ int a[32][32];}a1;int n,k,mod;Matrix mult2(Matrix A,Matrix B){ /// 矩阵乘法 Matrix C; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ C.a[i][j]=0; for(int k=0;k<n;k++){ C.a[i][j] += A.a[i][k]*B.a[k][j]; C.a[i][j] %= mod; } } } return C;}Matrix add(Matrix A,Matrix B){ /// 矩阵加法 Matrix C; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ C.a[i][j] = (A.a[i][j]+B.a[i][j])%mod; } } return C;}Matrix pow(Matrix a,int k){ /// 二分矩阵快速幂 if(k == 1)return a; if(k % 2)return mult2(pow(a,k-1),a); return pow(mult2(a,a),k/2);}Matrix sum(int k){ /// 二分快速求和 if(k<= 1) return a1; if(k % 2) return add(sum(k-1) , pow(a1,k)); else{ Matrix temp = sum(k/2); return add(temp , mult2(temp,pow(a1,k/2))); }}int main(){ int i,j; scanf("%d%d%d",&n,&k,&mod) ; for(i =0; i < n;i++) for(j =0 ;j < n;j++) scanf("%d",&a1.a[i][j]); Matrix ans; ans = sum(k); for(i =0 ;i< n;i++) { for(j=0 ;j < n - 1;j++) printf("%d ",ans.a[i][j]); printf("%d\n",ans.a[i][j]); } return 0;}/*2 2 40 1 1 1*/