P7657
035966_L3
·
·
题解
Picture
Main Solution
分类讨论题！放一张图（图在上面），我们慢慢来。
不要在意这个字迹……
如图 1，连接 3 \times n 的网格，可以先连个方框，再改掉一些边，塞进剩下 n-2 个点。
设 $a_i,b_i,c_i,d_i$ 分别为 $4$ 种状态下塞进前 $i$ 个点的状态数。
如图 $4$，考虑 $i=1$，可得初始状态：
$$\begin{cases} a_1=2, \\ b_1=2, \\ c_1=2, \\ d_1=0. \end{cases}$$
如图 $5$，考虑 $i=n-2$，可得答案 $X$ 的计算方式：
$$X=7a_{n-3}+7b_{n-3}+6c_{n-3}+6d_{n-3}$$
如图 $3$，考虑由 $i-1$ 转移到 $i$：
$$\begin{cases} a_i=2a_{i-1}+2b_{i-1}+2c_{i-1}+2d_{i-1}, \\ b_i=2a_{i-1}+2b_{i-1}+2c_{i-1}+2d_{i-1}, \\ c_i=a_{i-1}, \\ d_i=b_{i-1}. \end{cases}$$
于是，我们上矩阵快速幂计算就行了，如图 $6$：
$$\begin{bmatrix}2 \\ 2 \\ 2 \\ 0\end{bmatrix}
\times \begin{bmatrix}2 & 2 & 2 & 2 \\ 2 & 2 & 2 & 2 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix}^{n-4}=\begin{bmatrix}a_{n-3} \\ b_{n-3} \\ c_{n-3} \\ d_{n-3}\end{bmatrix}$$
记得特判 $n \le 4$。
**AC Code：**
```cpp
#include<bits/stdc++.h>
using namespace std;
const int P=1e9;
struct Square
{
int n,m;
long long a[5][5];
};
Square operator*(Square a,Square b)
{
if(a.m!=b.n) exit(-1);
int n=a.n,m=a.m,k=b.m;
Square c;
c.n=n,c.m=k;
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
c.a[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
for(int l=1;l<=m;l++)
c.a[i][j]+=a.a[i][l]*b.a[l][j],c.a[i][j]%=P;
return c;
}
Square operator^(Square a,long long b)
{
int n=a.n;
if(a.n!=a.m) exit(-1);
Square tmp[64];
tmp[0]=a;
for(int i=1;i<=63;i++)
tmp[i]=tmp[i-1]*tmp[i-1];
Square c;
c.n=c.m=n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
c.a[i][j]=(i==j);
for(long long i=0,j=1;i<=63;i++,j<<=1)
if(b&j) c=c*tmp[i];
return c;
}
int main()
{
int n;
cin>>n;
if(n==1) cout<<0;
if(n==2) cout<<1;
if(n==3) cout<<8;
if(n==4) cout<<40;
if(n<=4) return 0;
Square s=((Square){4,4,{{0,0,0,0,0},{0,2,2,2,2},{0,2,2,2,2},{0,1,0,0,0},{0,0,1,0,0}}})^(n-4);
Square t=s*((Square){4,1,{{0,0},{0,2},{0,2},{0,2},{0,0}}});
cout<<(7*t.a[1][1]+7*t.a[2][1]+6*t.a[3][1]+6*t.a[4][1])%P;
return 0;
}
```
# Extended Solution
很明显，当 $n \ge 2$ 时，$a_n=b_n$，$c_n=d_n=a_{n-1}$。
此时的初始状态是：
$$\begin{cases} a_1=2, \\ a_2=12. \end{cases}$$
答案 $X$ 的计算方式是：
$$X=14a_{n-3}+12a_{n-4}$$
由 $i-1$ 转移到 $i$：
$$a_i=4a_{i-1}+4a_{i-2}$$
于是，我们上矩阵快速幂计算就行了：
$$\begin{bmatrix}4 & 4 \\ 1 & 0\end{bmatrix}^{n-5} \times \begin{bmatrix}12 \\ 2\end{bmatrix}=\begin{bmatrix}a_{n-3} \\ a_{n-4}\end{bmatrix}$$
记得特判 $n \le 5$。
**AC Code：**
```cpp
#include<bits/stdc++.h>
using namespace std;
const int P=1e9;
struct Square
{
int n,m;
long long a[3][3];
};
Square operator*(Square a,Square b)
{
if(a.m!=b.n) exit(-1);
int n=a.n,m=a.m,k=b.m;
Square c;
c.n=n,c.m=k;
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
c.a[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
for(int l=1;l<=m;l++)
c.a[i][j]+=a.a[i][l]*b.a[l][j],c.a[i][j]%=P;
return c;
}
Square operator^(Square a,long long b)
{
int n=a.n;
if(a.n!=a.m) exit(-1);
Square tmp[64];
tmp[0]=a;
for(int i=1;i<=63;i++)
tmp[i]=tmp[i-1]*tmp[i-1];
Square c;
c.n=c.m=n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
c.a[i][j]=(i==j);
for(long long i=0,j=1;i<=63;i++,j<<=1)
if(b&j) c=c*tmp[i];
return c;
}
int main()
{
int n;
cin>>n;
if(n==1) cout<<0;
if(n==2) cout<<1;
if(n==3) cout<<8;
if(n==4) cout<<40;
if(n==5) cout<<192;
if(n<=5) return 0;
Square s=((Square){2,2,{{0,0,0},{0,4,4},{0,1,0}}})^(n-5);
Square t=s*((Square){2,1,{{0,0,0},{0,12,0},{0,2,0}}});
cout<<(14*t.a[1][1]+12*t.a[2][1])%P;
return 0;
}
```