题意: 求第 n 个三角形内部的上三角形个数
对每个三角形分别维护上下三角形个数, 记为 \(dp[1][i],dp[2][i]\)
规律很明显是
- \(dp[1][i+1]=3*dp[1][i]+dp[2][i]\)
- \(dp[2][i+1]=3*dp[2][i]+dp[1][i]\)
别忘了快速幂里也要 long long, 白送了个 TLE
- /*H E A D*/
- inline ll mod(ll a){return a%MOD;}
- struct Matrix{
- ll mt[5][5],r,c;
- void init(int rr,int cc,bool flag=0){
- r=rr;c=cc;
- memset(mt,0,sizeof mt);
- if(flag) rep(i,1,r) mt[i][i]=1;
- }
- Matrix operator * (const Matrix &rhs)const{
- Matrix ans; ans.init(r,rhs.c);
- rep(i,1,r){
- rep(j,1,rhs.c){
- int t=max(r,rhs.c);
- rep(k,1,t){
- ans.mt[i][j]+=mod(mt[i][k]*rhs.mt[k][j]);
- ans.mt[i][j]=mod(ans.mt[i][j]);
- }
- }
- }
- return ans;
- }
- };
- Matrix fpw(Matrix A,ll n){
- Matrix ans;ans.init(A.r,A.c,1);
- while(n){
- if(n&1) ans=ans*A;
- n>>=1;
- A=A*A;
- }
- return ans;
- }
- int bas[3][3]={
- {0,0,0},
- {0,3,1},
- {0,1,3},
- };
- int bas2[3]={0,1,0};
- ll n;
- int main(){
- Matrix A;A.init(2,2);
- rep(i,1,2) rep(j,1,2) A.mt[i][j]=bas[i][j];
- Matrix b; b.init(2,1);
- rep(i,1,2) b.mt[i][1]=bas2[i];
- while(cin>>n){
- Matrix res=fpw(A,n); res=res*b;
- ll ans=mod(res.mt[1][1]);
- println(ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2498989.html