前言
这道题给我平测了 \(3min+\)才出结果... 可真是逼死我了.
题目
题目链接: https://www.luogu.com.cn/problem/P5303
ITX351 要铺一条 \(2 \times N\) 的路, 为此他购买了 \(N\) 块 \(2 \times 1\) 的方砖. 可是其中一块砖在运送的过程中从中间裂开了, 变成了两块 \(1 \times 1\) 的砖块!
ITX351 由此产生了一个邪恶的想法: 他想要在这条路上故意把两块 \(1 \times 1\) 的砖块分开铺, 不让两块砖有相邻的边, 其他砖块可以随意铺, 直到整条路铺满. 这样一定可以逼死自身强迫症 sea5!
也许下面的剧情你已经猜到了 -- 他为此兴奋不已, 以至于无法敲键盘. 于是, 他请你帮忙计算一下, 有多少种方案可以让自己的阴谋得逞.
思路
数据范围明显提示这道题是矩阵乘法.
有一个十分明显的结论, 假设两个 \(1\times 1\)的方砖分别位于第 \(i,j\)列 (\(i<j\) 且 \(j-i\geq 2\)), 那么第 \(i\sim j\)列仅有 \(2\)种放法, 前 \(i-1\)列有 \(fib[i-1]\)种放法.
证明:
如果第 \(i\sim j\)列中有一列是竖着摆放方砖的, 那么显然会把第 \(i\sim j\)列构成的矩形分为两个大小为奇数的部分, 而每一个 \(1\times 2\)方砖的大小为偶数, 所以肯定铺不满. 所以只能横着放.
而横着放时不可以中间空一格否则就永远无法填满, 所以必须一个接着一个放. 画图后容易发现要满足这些要求只有 \(2\)中情况.
前 \(i-1\)列只能用 \(1\times 2\)的方砖摆放, 摆放的方案其实只有 "在最后一列加上一个 \(1\times 2\)的方砖" 和 "在最后一个 \(2\times 2\)的正方形中横着放两块方砖", 设用 \(2\times 1\)的方砖摆放 \(2\times i\)的路面的方案数为 \(g[i]\), 那么就有 \(g[i]=g[i-1]+g[i-2]\), 边界为 \(g[1]=1,g[2]=2\). 容易发现这是一个斐波那契数列, 前 \(i-1\)列有 \(fib[i-1]\)种放法.
证毕.
先写出递推式. 设 \(f[i]\)表示 \(n=i\)时的方案数. 那么有三种情况.
在最后一列加上一个 \(1\times 2\)的方砖, 共 \(f[i-1]\)种方案.
在最后一个 \(2\times 2\)的正方形中横着放两块方砖 (竖着放其实就是第一种情况), 共 \(f[i-2]\) 种情况.
在最后一列放一个 \(1\times 1\)的方砖. 假设另一个 \(1\times 1\)的方砖放在第 \(j\)列, 根据上文的结论, 有方案数 =\(2\sum^{i-3}_{j=1}fib[j]\).
所以我们就得到了递推式
\[f[i]=f[i-1]+f[i-2]+\sum^{i-2}_{j=1}fib[j]\]
其中 \(fib[0]=fib[1]=1,fib[i]=fib[i-1]+2fib[i-2](i>1)\).
那么可以构建一个 \(5\times 5\)的矩阵, 分别表示 \(f[i],f[i-1],s[i-3],fib[i-3],fib[i-4]\), 其中 \(s[x]\)表示前 \(x\)个斐波那契数之和.
那么转移矩阵如下
\[\begin{bmatrix} 1& 1 & 0 & 0 & 0\\ 1& 0 & 0 & 0 & 0\\ 2& 0 & 1 & 0 & 0\\ 0& 0 & 1 & 1 & 1\\ 0& 0 & 1 & 1 & 0 \end{bmatrix}\]
初始矩阵如下
\[\begin{bmatrix} 6 & 2 &4 &2 &1 \end{bmatrix}\]
时间复杂度 \(O(Tm^3\log n)\), 其中 \(m=5\).
代码
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- const int MOD=1000000007,N=6;
- int n,T;
- struct matrix
- {
- int a[N][N];
- friend matrix operator *(matrix a,matrix b)
- {
- matrix c;
- memset(c.a,0,sizeof(c.a));
- for (int i=1;i<N;i++)
- for (int j=1;j<N;j++)
- for (int k=1;k<N;k++)
- c.a[i][j]=(c.a[i][j]+1LL*a.a[i][k]*b.a[k][j]%MOD)%MOD;
- return c;
- }
- }a,f,A,F;
- void power(int k)
- {
- for (;k;k>>=1,a=a*a)
- if (k&1) f=f*a;
- }
- int main()
- {
- A.a[1][1]=A.a[1][2]=A.a[2][1]=A.a[3][3]=A.a[4][3]=A.a[4][4]=A.a[4][5]=A.a[5][3]=A.a[5][4]=1;
- A.a[3][1]=2;
- F.a[1][1]=6; F.a[1][2]=2; F.a[1][3]=4; F.a[1][4]=2; F.a[1][5]=1;
- scanf("%d",&T);
- while (T--)
- {
- scanf("%d",&n);
- if (n==1 || n==2) printf("0\n");
- else if (n==3) printf("2\n");
- else if (n==4) printf("6\n");
- else
- {
- memcpy(a.a,A.a,sizeof(a.a));
- memcpy(f.a,F.a,sizeof(f.a));
- power(n-4);
- printf("%d\n",f.a[1][1]);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3392839.html