自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:31:55，当前版本为作者最后更新于2024-02-12 17:22:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Picture

Main Solution

分类讨论题！放一张图（图在上面），我们慢慢来。

不要在意这个字迹……

如图 $1$，连接 $3 \times n$ 的网格，可以先连个方框，再改掉一些边，塞进剩下 $n-2$ 个点。

$n-2$ 个点中，最左边和最右边的点单独考虑，剩下的 $n-4$ 个点塞进去的方式有 $4$ 种，如图 $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：

#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：

#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;
}