[abmfy]新宝岛

xixihaha2021 · 2024-04-07 21:31:17 · 个人记录

[abmfy]新宝岛

题意简述

初始状态为1，进行n次转移，问最终状态为1的方案数对 10^9+7 取模的结果。下面给出转移方式：

• 当前状态为1，转移后状态为2或3；
• 当前状态为2，转移后状态为1；
• 当前状态为3，转移后状态为1或2或3.

  思路简述

  考虑转移矩阵 A=\begin{bmatrix}0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{bmatrix}，因此考虑矩阵乘幂。

设 ans_i 表示最终状态为 i 的方案数，初始数组 B=\begin{Bmatrix} 1 & 0 & 0 \end{Bmatrix}，显然有

即答案为

矩阵乘幂简介：

• 设存在两个矩阵 A,B，定义其行数分别为 row_A,row_B，列数分别为 col_A,col_B。

• AB=C \iff col_A=row_B \land C_{i,j}=\sum_{k=1}^{col_A} A_{i,k} \cdot B_{k,j}.

• 矩阵乘方指对于 A^n，讨论 2|n 是否成立，类似快速幂求解。（矩阵乘方有意义的条件：A 为方阵；形式：递归/循环。）

  复杂度分析

  时间复杂度分析

  显然，矩阵快速幂的时间复杂度即算法时间复杂度，即O(\log_2 N)。

  空间复杂度分析

  显然，算法的空间复杂度为 O(1)。

  数据范围

  1 \le n \le 10^9.

对于时间，显然时间复杂度随着变量的增大单调递增，因此当 n 取最大值 10^9 时，时间复杂度最大，即 \log_2 10^9 \approx 30=3 \times 10<4 \times 10^8，所以不会超时。

对于空间，显然空间复杂度与变量的增大无关，所以不会超空间。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[3][3] = {{0,1,1},{1,0,0},{1,1,1}},b[3] = {1,0,0},dp[3],c[3][3],res[3][3];
int main(){
    memset(res,0,sizeof(res));
    scanf("%lld",&n);
    for(ll i = 0;i <= 2;i++)res[i][i] = 1;
    while(n){
        if(n % 2 == 1){
            memset(c,0,sizeof(c));
            for(ll i = 0;i <= 2;i++)for(ll j = 0;j <= 2;j++)for(ll k = 0;k <= 2;k++)c[i][j] = (c[i][j] + res[i][k] * a[k][j] % 1000000007) % 1000000007;
            for(ll i = 0;i <= 2;i++)for(ll j = 0;j <= 2;j++)res[i][j] = c[i][j];
        }
        memset(c,0,sizeof(c));
        for(ll i = 0;i <= 2;i++)for(ll j = 0;j <= 2;j++)for(ll k = 0;k <= 2;k++)c[i][j] = (c[i][j] + a[i][k] * a[k][j] % 1000000007) % 1000000007;
        for(ll i = 0;i <= 2;i++)for(ll j = 0;j <= 2;j++)a[i][j] = c[i][j];
        n /= 2;
    }
    for(ll i = 0;i <= 2;i++)for(ll j = 0;j <= 2;j++)dp[i] = (dp[i] + res[i][j] * b[j] % 1000000007) % 1000000007;
    printf("%lld",dp[0]);
    return 0;
}