看到 \(N\leq 2\times 10^9\) 的范围,一眼矩阵快速幂优化 DP。
首先考虑朴素 DP 怎么写。根据题目所给信息,我们设 \(dp_{i,0}\) 表示前面 \(i\) 个方砖,并且已经使用了 \(2\) 个 \(1\times 1\) 的方砖,\(dp_{i,1}\) 则表示前面 \(i\) 个方砖,没有使用任何一个 \(1\times 1\) 的方砖。
为了转移至 \(dp_{i,0}\),既然已经使用过了 \(2\) 个 \(1\times 1\) 的方砖,那么我们剩下的都是 \(1\times 2\) 的方砖,对于这样的方砖,我们有两种可行的摆放,一种是直接竖着放,可以由 \(dp_{i-1,0}\) 转移得到;另一种是两个横着放,可以由 \(dp_{i-2,0}\) 得到。而我们还可以在 \([1,i-3]\) 选择一个 \(j\),然后利用后面的区间 \([j+1,i]\) 放置两个 \(1\times 1\) 的方砖,且两个方砖放置的位置分别在第 \(j+1\) 列和第 \(i\) 列。而我们不难发现有两种情况,一种是这个区间长度为奇数,另一种是区间长度为偶数。
对于奇数长度的区间,我们可以让两个方砖放在不同的行,这里各自的行剩下的长度就是偶数(奇数减一是偶数),我们就每行横着放 \(1\times 2\) 的方砖就可以了。而如果放在同一行,那么我们就无法填满里面的空缺(可以自己画图理解一下)。对于偶数长度的区间,我们可以让两个方砖在同一行,这样上下两行剩余的长度就都是偶数了,就可以横着放 \(1\times 2\) 的方砖来填满空缺,反之如果是在不同的行,那么我们就不可以完成。
如果实在理解不了,我可以给一点提示,就是当区间两边填了 \(1\times 1\) 的方砖后,那么对于所填方砖的另外一行,我们只可能使用 \(1\times 2\) 的方砖填满那个 \(1\times 1\) 的空缺,而此时又会产生新的 \(1\times 1\) 的空缺……以此类推。(这样提示还不够,那我可能就帮不了你了。。)
总之我们可以发现,不管是放在不同的行或者相同的行,都会得到 \(2\) 种答案。而且此时我们转移的是 \(dp_{j,1}\),因为如果在 \([j+1,i]\) 放置两个裂开的砖块,那么 \([1,j]\) 肯定就是没有裂开的砖块的。
而我们的 \(dp_{i,1}\) 就非常好转移了,就是要么竖着放,要么两个横着放,即 \(dp_{i,1}=dp_{i-1,1}+dp_{i-2,1}\)。
所以我们列出方程:
\[\begin{cases} dp_{i,0}=dp_{i-1,0}+dp_{i-2,0}+2\times \sum _{j=1}^{i-3}dp_{j,1}\\ dp_{i,1}=dp_{i-1,1}+dp_{i-2,1} \\\end{cases} \]但是这样肯定是会超时的,所以就会想到使用矩阵。
但是我们又发现这个 \(dp_{i,0}\) 的转移不是 \(O(1)\) 的,所以考虑将方程进行改造。对于 \(\sum _{j=1}^{i-3}dp_{j,1}\),我们不难发现每次 \(i\) 增加 \(1\),我们原来的值就会增加一个 \(dp_{j,1}\) 的值。根据这个形式,我们就想到使用前缀和储存这个区间值。设 \(sum_i\) 表示 \(\sum_{j=1}^i dp_{j,1}\) 的值。原方程变为:
\[dp_{i,0}=dp_{i-1,0}+dp_{i-2,0}+2\times sum_{i-3} \]我们将一次转移使用到的值提出来:\(dp_{i-1,0}\),\(dp_{i-2,0}\),\(sum_{i-3}\),\(dp_{i-1,1}\),\(dp_{i-2,1}\)。然后利用这些值构造初始矩阵:
\[\left( \begin{matrix} dp_{i-1,0} & dp_{i-2,0} & dp_{i-1,1} & dp_{i-2,1} & sum_{i-3} \end{matrix} \right) \]换成具体的数值,真正的初始矩阵是:
\[\left( \begin{matrix} 0 & 0 & 2 & 1 & 1 \end{matrix} \right) \]注意这个 \(sum_0\) 是 \(1\),因为放置 \(0\) 个方砖也是一种答案。
每次转移按照上述方程进行转移,得到转移矩阵:
\[\left( \begin{matrix} 1 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 1\\ 2 & 0 & 0 & 0 & 1 \end{matrix} \right) \]所以得到答案为:
\[\left( \begin{matrix} 0 & 0 & 2 & 1 & 1 \end{matrix} \right) \times \left( \begin{matrix} 1 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 1\\ 2 & 0 & 0 & 0 & 1 \end{matrix} \right) ^{n-2} \]这样代码就非常简单了:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1e9+7;
long long n,p,q;
void mul(long long f[5],long long a[5][5])
{
long long c[5];
memset(c,0,sizeof(c));
for(int j=0;j<5;j++)
{
for(int k=0;k<5;k++) c[j]=(c[j]+f[k]*a[k][j])%MOD;
}
memcpy(f,c,sizeof(c));
}
void mulself(long long a[5][5])
{
long long c[5][5];
memset(c,0,sizeof(c));
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
for(int k=0;k<5;k++) c[i][j]=(c[i][j]+(long long)a[i][k]*a[k][j])%MOD;
}
}
memcpy(a,c,sizeof(c));
}
signed main()
{
long long T;
cin>>T;
while(T--)
{
cin>>n;
long long f[5]={0,0,2,1,1};
long long a[5][5]={0};
a[0][0]=a[0][1]=a[1][0]=a[2][2]=a[2][3]=a[3][2]=a[3][4]=a[4][4]=1,a[4][0]=2;
if(n==1||n==2||!n)
{
puts("0");
continue;
}
n-=2;
while(n)
{
if(n&1) mul(f,a);
mulself(a);
n>>=1;
}
cout<<f[0]<<endl;
}
return 0;
}
标签:matrix,题解,sum,强迫症,long,times,GZOI2019,dp,方砖
From: https://www.cnblogs.com/SuporShoop/p/18435409