[洛谷 5303,loj 3086][GXOI/GZOI2019]逼死强迫症

题目链接

https://www.luogu.com.cn/problem/P5303

https://loj.ac/problem/3086

题解

神仙推式子题。

容易发现整个区域可以分为三部分:第一个 \(1 \times 1\) 方块左边,两个 \(1 \times 1\) 方块中间部分(至少 \(2 \times 3\) 的区域),第二个 \(1 \times 1\) 方块右边部分。

如下图所示:

其中两个 \(1 \times 1\) 方块是同行还是异行取决于中间列数的奇偶性(奇数为异行,偶数为同行)。

如果两个 \(1 \times 1\) 方块的位置定下来了,上图中间的红色区域就只有一种摆法。

而左边黑色区域和右边绿色区域,显然分别有 \(F_x,F_y\) 种摆法(\(F_x\) 为斐波那契数列,满足 \(F_0=F_1=1\),\(F_i=F_{i-1}+F_{i-2}\))。

根据乘法原理,答案可以表示为:

$$2 \sum_{x=0}^{n-3} \sum_{y=0}^{n-x-3}F_x \times F_y$$

(中间的红色区域考虑上下行交换,所以答案乘二)

运用乘法分配律:

$$2 \sum_{x=0}^{n-3}F_x \sum_{y=0}^{n-x-3}F_y$$

斐波那契数列满足 \(\sum_{i=0}^x F_i=F_{x+2}-1\),所以把后面的 \(\sum F_y\) 换掉:

$$2 \sum_{x=0}^{n-3}F_x \times (F_{n-x-1}-1)$$

整理后得到:

$$2 (\sum_{x=0}^{n-3}F_x \times F_{n-x-1}-F_{n-1}+1)$$

现在重点放到 \(\sum_{x=0}^{n-3}F_x \times F_{n-x-1}\) 上。

我们设:

$$G_n=\sum_{x=0}^{n}F_x \times F_{n-x}$$

将 \(x=n\) 和 \(x=n-1\) 提出来:

$$G_n=\sum_{x=0}^{n-2}F_x \times F_{n-x} + F_n+F_{n-1}$$

把 \(F_{n-x}\) 也拆开:

$$G_n=\sum_{x=0}^{n-2}F_x \times (F_{n-x-1}+F_{n-x-2})+F_n+F_{n-1}$$

用乘法分配律:

$$G_n=\sum_{x=0}^{n-2}F_x \times F_{n-x-1}+\sum_{x=0}^{n-2}F_x \times F_{n-x-2}+F_n+F_{n-1}$$

把 \(F_{n-1}\) 放回到式子的第一块:

$$G_n=\sum_{x=0}^{n-1}F_x \times F_{n-x-1}+\sum_{x=0}^{n-2}F_x \times F_{n-x-2}+F_n$$

到这里终于豁然开朗啦。

$$G_n=G_{n-1}+G_{n-2}+F_n$$

把 \(G_n\) 代入到答案中,可得答案为:

$$2(1+G_{n-1}-2 \times F_{n-1}-F_{n-2})$$

最后的问题就是用矩阵快速幂来递推 \(F_n,G_n\) 了。

稍微推一下就能得到:

$$\begin{bmatrix} F_{n-1} & F_{n-2} & F_{n-3} & G_{n-1} & G_{n-2} & G_{n-3} \end{bmatrix} \\ \times \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} \\ = \begin{bmatrix} F_n & F_{n-1} & F_{n-2} & G_n & G_{n-1} & G_{n-2} \end{bmatrix}$$

时间复杂度 \(O(6^3 T\log n)\)。

#include <cstring>
#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
struct mat
{
 long long a[15][15];
 mat(int x=0)
 {
  memset(a,0,sizeof(a));
  for(int i=1;i<=6;i++)
   a[i][i]=x;
 }
 mat operator*(const mat&A)const
 {
  mat ans;
  for(int k=1;k<=6;k++)
   for(int i=1;i<=6;i++)
    for(int j=1;j<=6;j++)
     ans.a[i][j]=(ans.a[i][j]+a[i][k]*A.a[k][j])%MOD;
  return ans;
 }
}f,g;
void init()
{
 //[f_3,f_2,f_1,g_3,g_2,g_1]
 f.a[1][1]=3,f.a[1][2]=2,f.a[1][3]=1,f.a[1][4]=10,f.a[1][5]=5,f.a[1][6]=2;
 /*
 1 1 0 1 0 0
 1 0 1 1 0 0
 0 0 0 0 0 0
 0 0 0 1 1 0
 0 0 0 1 0 1
 0 0 0 0 0 0
 */
 g.a[1][1]=1,g.a[1][2]=1,g.a[1][3]=0,g.a[1][4]=1,g.a[1][5]=0,g.a[1][6]=0;
 g.a[2][1]=1,g.a[2][2]=0,g.a[2][3]=1,g.a[2][4]=1,g.a[2][5]=0,g.a[2][6]=0;
 g.a[3][1]=0,g.a[3][2]=0,g.a[3][3]=0,g.a[3][4]=0,g.a[3][5]=0,g.a[3][6]=0;
 g.a[4][1]=0,g.a[4][2]=0,g.a[4][3]=0,g.a[4][4]=1,g.a[4][5]=1,g.a[4][6]=0;
 g.a[5][1]=0,g.a[5][2]=0,g.a[5][3]=0,g.a[5][4]=1,g.a[5][5]=0,g.a[5][6]=1;
 g.a[6][1]=0,g.a[6][2]=0,g.a[6][3]=0,g.a[6][4]=0,g.a[6][5]=0,g.a[6][6]=0;
}
mat fpow(mat x,int y)
{
 mat ans(1);
 while(y)
 {
  if(y&1)ans=ans*x;
  x=x*x;
  y>>=1;
 }
 return ans;
}
int main()
{
 int t;
 cin>>t;
 init();
 while(t--)
 {
  int n;
  cin>>n;
  if(n<=2)cout<<0<<endl;
  else
  {
   mat res=f*fpow(g,n-3);
   cout<<(2*(-2*res.a[1][2]-res.a[1][3]+res.a[1][5]+1)%MOD+MOD)%MOD<<endl;
  }
 }
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据