出题人题解|拆卸爆能器

T4_拆卸爆能器 题解

对于题目里面那张图片，设左边的叫A拼图，右边的叫B拼图。

测试点 $1\sim 2,3\sim 5$

考虑朴素 $dp$。定义 $dp(i)$ 表示放满 $2\times i$ 的方格的方案数。

考虑手玩多出的第 $i$ 列的摆法来转移，有如下方案：

第 $i$ 列直接竖着摆A

有方案数 $dp(i-1)$

• 第一行横着放A，第二行也横着放A

有方案数 $dp(i-2)$

有放B的情况

此时一定是左右放B，中间插入若干个A，如下图

这样的方案数是

$$\sum_{j=0}^{i-3} dp_j$$

然后把图片中两种情况垂直翻转后依旧成立，所以方案数 $\times 2$，得到转移

$dp_i=dp_{i-1}+dp_{i-2}+2\sum\limits_{j=0}^{i-3} a_i$

这个转移是 $O(n^2)$ 的，可以通过测试点 $1\sim 2$。但是 $dp_j$ 总和的计算可以用前缀和来优化成 $O(1)$，这样就一并通过了测试点 $3\sim 5$。

#include<bits/stdc++.h>					
using namespace std;					
#define int long long					
constexpr int mod = 1e9+7;					
int dp[1000009];					
int sum[1000009];					
int N[11],maxn;					
signed main(){					
    int _;					
    cin>>_;					
    for(int i = 1;i<=_;++i){					
        cin>>N[i];					
        maxn = max(N[i],maxn);					
    }					
    dp[0] = 1,dp[1] = 1,dp[2] = 2;					
    sum[0] = 1,sum[1] = 2,sum[2] = 4;					
    for(int i = 3;i<=maxn;++i){					
        dp[i] = 2*sum[i-3]%mod+dp[i-1]+dp[i-2];					
        dp[i]%=mod;					
        sum[i] = sum[i-1]+dp[i];					
        sum[i]%=mod;					
    }					
    for(int i = 1;i<=_;++i){					
        cout<<dp[N[i]]<<'\n';					
    }					
}					

时间复杂度：$O(Tn)$

---

测试点 $6\sim 10$

请选手先自行学习：“矩阵快速幂”

考虑如下矩阵的转移，$s$ 表示 $dp$ 数组的前缀和：

$$\begin{align*} \begin{bmatrix} dp_{i-1} \\ dp_{i-2} \\ s_{i-3} \end{bmatrix} \rightarrow \begin{bmatrix} dp_i \\ dp_{i-1} \\ dp_{i-2} \end{bmatrix} \end{align*}$$

• $dp_i=dp_{i-1}+dp_{i-2}+2\sum\limits_{j=0}^{i-3} a_i$

得到矩阵系数 $[1\ 1\ 2]$

• $dp_{i-1}=dp_{i-1}$

得到矩阵系数 $[1\ 0\ 0]$

• $s_{i-2}=s_{i-3}+f_{i-2}$

得到矩阵系数 $[0\ 1\ 1]$

综上：

$$\begin{align*} \begin{bmatrix} f_i \\ f_{i-1} \\ s_{i-2} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 2 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{bmatrix} \times \begin{bmatrix} f_{i-1} \\ f_{i-2} \\ s_{i-3} \end{bmatrix} \end{align*}$$

于是上矩阵快速幂即可。

#include<bits/stdc++.h>					
#define int long long					
using namespace std;					
const int mod = 1e9+7;					
struct matrix{					
	int a[3][3];				
	void make(){				
		memset(a,0,sizeof a);			
		for(int i = 0;i<3;++i){			
			a[i][i] = 1;		
        }					
	}				
	matrix operator*(const matrix &x)const{				
		matrix ans;			
		for(int i = 0;i<3;++i){			
			for(int j = 0;j<3;++j){		
				ans.a[i][j] = 0;	
				for(int k = 0;k<3;++k){	
					ans.a[i][j] = (ans.a[i][j]+a[i][k]*x.a[k][j])%mod;
                }					
			}		
        }					
		return ans;			
	}				
	matrix operator^(int y)const{				
		matrix ans,x = *this;			
		ans.make();			
		while(y){			
			if(y&1) ans = ans*x;		
			y>>=1;		
			x = x*x;		
		}			
		return ans;			
	}				
}A;					
signed main(){					
    int _;					
    cin>>_;					
    while(_--){					
    	int n;				
    	cin>>n;				
    	A.a[0][0] = 1,A.a[0][1] = 1,A.a[0][2] = 2;				
    	A.a[1][0] = 1,A.a[1][1] = 0,A.a[1][2] = 0;				
    	A.a[2][0] = 0,A.a[2][1] = 1,A.a[2][2] = 1;				
    	A = A^n;				
    	cout<<A.a[0][0]<<'\n';				
    }					
}					

时间复杂度：$O(Tlogn)$