这两种快速幂写法，matpow_1会在大的数据下超时 ，matpow_2就会AC ，为啥呢？

	matrix matpow_1(LL p) {//matrix fast power
		uint r=0;matrix ret=Identity(n),Now=*this;
		while(p) {
			if(p&(1<<r)) {
				ret=ret*Now;
				p-=(1<<r);
			}
			Now=Now*Now;
			r++;
		}
		return ret;
	}
	matrix matpow_2(LL p) {//matrix fast power
		matrix ret=Identity(n),Now=*this;
		while(p) {
			if(p&1) {
				ret=ret*Now;
			}
			Now=Now*Now;
			p>>=1;
		}
		return ret;
	}

总体代码如下：

#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
typedef unsigned int uint;
const LL mod=1e9+7;

class matrix {
private:
	uint n;
	vector<vector<LL>> mat;
public:
	matrix(vector<vector<LL>> V) {
		mat=V;
		n=V.size();
	}
	matrix operator *(matrix R) {
		vector<vector<LL>> V;
		for(uint i=0;i<n;i++) {
			vector<LL> arr;arr.clear();
			for(uint j=0;j<n;j++) {
				LL num=0;
				for(uint k=0;k<n;k++) {
					num+=mat[i][k]*R.mat[k][j];
					num%=mod;
				}
				arr.push_back(num);
			}
			V.push_back(arr);
		}
		return matrix(V);
	}
	matrix Identity(uint k) {//Get a kxk identity matrix 
		vector<vector<LL>> V;
		for(uint i=0;i<k;i++) {
			vector<LL> arr;arr.clear();
			for(uint j=0;j<k;j++) {
				if(i==j) arr.push_back(1);
				else arr.push_back(0);
			}
			V.push_back(arr);
		}
		return matrix(V);
	}
	matrix matpow_1(LL p) {//matrix fast power
		uint r=0;matrix ret=Identity(n),Now=*this;
		while(p) {
			if(p&(1<<r)) {
				ret=ret*Now;
				p-=(1<<r);
			}
			Now=Now*Now;
			r++;
		}
		return ret;
	}
	matrix matpow_2(LL p) {//matrix fast power
		matrix ret=Identity(n),Now=*this;
		while(p) {
			if(p&1) {
				ret=ret*Now;
			}
			Now=Now*Now;
			p>>=1;
		}
		return ret;
	}
	void print() {//print this matrix
		for(uint i=0;i<n;i++) {
			cout<<"";
			for(uint j=0;j<n-1;j++) {
				cout<<mat[i][j]<<' ';
			}
			cout<<mat[i][n-1]<<"\n";
		}
	}
};
uint n;LL k;
LL intpow(LL a,LL k) {
	LL r=0,ret=1,A=a;
	while(k) {
		if(k&(1<<r)) {
			ret*=A;
			k-=(1<<r);
		}
		A*=A;
		r++;
	}
	return ret;
}
int main() {
	cin>>n>>k;
	vector<vector<LL>> V;
	for(uint i=0;i<n;i++) {
		vector<LL> arr;arr.clear();//row vwctor
		for(uint j=0;j<n;j++) {
			LL num;cin>>num;
			arr.push_back(num);
		}
		V.push_back(arr);
	}
	matrix mat(V);
//	mat.print();
	matrix ret=mat.matpow_2(k);
	ret.print();
 	return 0;
}

OWO