//首先，感谢Q巨
定义状态向量b[6]
b[0]:三面临红色的蓝色三角形个数
b[1]:两面临红色且一面临空的蓝色三角形个数
b[2]:一面临红色且两面临空的蓝色三角形个数
b[3]:三面临红色的黄色三角形个数
b[4]:两面临红色且一面临绿+的黄色三角形个数
b[5]:一面临红色且两面临绿+的黄色三角形个数
转移矩阵：
[3 1 0 0 0 0;
0 2 2 0 0 0;
0 1 3 0 0 0;
3 2 1 0 0 0;
0 0 0 6 3 0;
0 0 0 0 2 4]
最朴素的TLE代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
;
;
LL b[N]= {,,,,,}; //此处初始化列向量
LL hh[N][N]={{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,}
};
struct Mat
{
LL mat[N][N];
} A;
Mat Mut(Mat a,Mat b)
{
Mat c;
memset(c.mat,,sizeof(c.mat));
; k<N; k++)
; i<N; i++)
if(a.mat[i][k])
; j<N; j++)
{
c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]%mod;
c.mat[i][j]=c.mat[i][j]%mod;
}
return c;
}
Mat Qpow(Mat a,LL n)
{
Mat c;
; i<N; ++i)
; j<N; ++j)
c.mat[i][j]=(i==j);
)
{
) c=Mut(c,a);
a=Mut(a,a);
}
return c;
}
void cal(Mat A,LL n,LL b[],LL& Fn,LL& Gn)
{
Mat A_=Qpow(A,n-);
Fn=Gn=;
LL c[N]={};
;i<N;i++)
;j<N;j++)
c[i]=(c[i]+A_.mat[i][j]*b[j])%mod;
Fn=(c[]+c[]+c[])%mod;
Gn=(c[]+c[]+c[])%mod;
}
void init_A()
{
;i<N;i++)
;j<N;j++)
A.mat[i][j]=hh[i][j];
}
int main()
{
LL n,Fn,Gn;
init_A();
while(cin>>n)
{
)
{
puts("1 0");
continue;
}
n--;
cal(A,n,b,Fn,Gn);
cout<<Fn<<' '<<Gn<<endl;
}
}
貌似（只是貌似）被优化但仍然TLE的代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
;
;
LL b[N]= {,,,,,}; //此处初始化列向量
LL hh[N][N]={{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,}
};
struct Mat
{
LL mat[N][N];
} A,F[];
void printM(Mat x)
{
puts("=================================================================");
;i<N;i++)
{
;j<N;j++)
printf("%10lld",x.mat[i][j]);
puts("");
}
}
Mat Mut(Mat a,Mat b)
{
Mat c;
memset(c.mat,,sizeof(c.mat));
; k<N; k++)
; i<N; i++)
if(a.mat[i][k])
; j<N; j++)
{
c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]%mod;
c.mat[i][j]=c.mat[i][j]%mod;
}
return c;
}
Mat Qpow(Mat a,LL n)
{
Mat c;
; i<N; ++i)
; j<N; ++j)
c.mat[i][j]=(i==j);
)
{
) c=Mut(c,a);
a=Mut(a,a);
}
return c;
}
void cal(Mat A,LL n,LL b[],LL& Fn,LL& Gn)
{
Mat A_;
; i<N; ++i)
; j<N; ++j)
A_.mat[i][j]=(i==j);
;i<&&n;i++,n>>=)
) A_=Mut(A_,F[i]);
//printM(A_);
Fn=Gn=;
LL c[N]={};
;i<N;i++)
;j<N;j++)
c[i]=(c[i]+A_.mat[i][j]*b[j])%mod;
Fn=(c[]+c[]+c[])%mod;
Gn=(c[]+c[]+c[])%mod;
}
void init_A()
{
;i<N;i++)
;j<N;j++)
A.mat[i][j]=hh[i][j];
F[]=A;
;i<;i++)
F[i]=Mut(F[i-],F[i-]);
}
int main()
{
LL n,Fn,Gn;
init_A();
int T;
// cin>>T;
scanf("%lld",&T);
while(T--)
{
// cin>>n;
scanf("%lld",&n);
)
{
puts("1 0");
continue;
}
n-=;
cal(A,n,b,Fn,Gn); // cout<<Fn<<' '<<Gn<<endl;
printf("%lld %lld\n",Fn,Gn);
}
}
矩阵相乘一次的复杂度是O(N^3)的，不过预处理2^i（i：0~60）的矩阵后，可以用向量记录中间结果，而矩阵*向量的复杂度为O(N^2)
最终复杂度： O(T * lb(n) * N^2)->O(1e5 * 60 * 36)->O(2e8)
最终可以AC的代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
;
;
LL b[N]= {,,,,,}; //此处初始化列向量
LL hh[N][N]={{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,}
};
struct Mat
{
LL mat[N][N];
} A,F[];
void printM(Mat x)
{
puts("=================================================================");
;i<N;i++)
{
;j<N;j++)
printf("%10lld",x.mat[i][j]);
puts("");
}
}
Mat Mut(Mat a,Mat b)
{
Mat c;
memset(c.mat,,sizeof(c.mat));
; k<N; k++)
; i<N; i++)
if(a.mat[i][k])
; j<N; j++)
{
c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]%mod;
c.mat[i][j]=c.mat[i][j]%mod;
}
return c;
}
Mat Qpow(Mat a,LL n)
{
Mat c;
; i<N; ++i)
; j<N; ++j)
c.mat[i][j]=(i==j);
)
{
) c=Mut(c,a);
a=Mut(a,a);
}
return c;
}
void cal(Mat A,LL n,LL b[],LL& Fn,LL& Gn)
{
Mat A_;
LL c[N]={,,,,,};
; i<N; ++i)
; j<N; ++j)
A_.mat[i][j]=(i==j);
;i<&&n;i++,n>>=)
)
{
LL tres[]={,,,,,};
;j<;j++) //矩阵的行
;k<;k++) //矩阵的列
tres[j]=(tres[j]+F[i].mat[j][k]*c[k])%mod;
;j<;j++)
c[j]=tres[j]%mod;
}
Fn=Gn=;
Fn=(c[]+c[]+c[])%mod;
Gn=(c[]+c[]+c[])%mod;
}
void init_A()
{
;i<N;i++)
;j<N;j++)
A.mat[i][j]=hh[i][j];
F[]=A;
;i<;i++)
F[i]=Mut(F[i-],F[i-]);
}
int main()
{
LL n,Fn,Gn;
init_A();
int T;
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&n);
)
{
puts("1 0");
continue;
}
n-=;
cal(A,n,b,Fn,Gn);
printf("%lld %lld\n",Fn,Gn);
}
}