P4910 题解

· · 题解

前言

题目传送门！

更好的阅读体验？

矩阵快速幂优化 DP 经典题。

前置知识：会做简单的 DP、矩阵加速。

题目简述

给定一个长度为 n 的环，每个位置可以填 1 或 2。相邻两个不能同时填 1。

求方案数。多测。

朴素 DP

思路

看到题目，很容易想到环形 DP。

设 dp_{i, 0} 表示第 i 位填 1 的总方案数，dp_{i, 1} 表示第 i 位填 2 的总方案数。

状态转移方程如下：

初始化要分类讨论一下：

把公式抄上去即可。时间复杂度 O(n)。

代码

按照题目的应该是可以拿 60 分的。但是只有 48 分。

提交记录。

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, dp[N][2]; //dp[i][0/1] : 第i位填A或B
void calc()
{
    for (int i = 2; i <= n; i++)
        dp[i][0] = dp[i - 1][1],                        //第i位填1，则上一位只能填2
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % mod; //第i位填2，则上一位可以填1或2
}
void solve()
{
    long long ans = 0;
    scanf("%d", &n);

    dp[1][0] = 1, dp[1][1] = 0;           //第一位填1，
    calc(), ans = (ans + dp[n][1]) % mod; //则最后一位只能填2

    dp[1][0] = 0, dp[1][1] = 1;                      //第一位填2，
    calc(), ans = (ans + dp[n][0] + dp[n][1]) % mod; //则最后一位可以填1或2

    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

矩阵加速

思路

如果 n 就 10^6，那顶多一道黄题。但是 n 是 10^{18}，哭泣。

这里用一个很常见的 trick：矩阵加速优化 DP。

我们设一组矩阵 \begin{pmatrix} dp_{i, 0} & dp_{i, 1} \end{pmatrix}。

然后很容易根据状态转移方程列出关系式：

\begin{pmatrix} dp_{i, 0} & dp_{i, 1} \end{pmatrix} \times \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} dp_{i+1, 0} & dp_{i+1, 1} \end{pmatrix}

再根据矩阵跑快速幂就秒掉了这题。

同上面的，仍然是要初始化两个（具体看代码）。

时间复杂度 O(\log n \times t^3)，t = 2（矩阵大小）。

你会发现这东西很小很小，所以随便过。

代码

很轻松拿到 100 分。跑得飞快，最慢的点 4 毫秒。

代码轻度整活，但是应该可以看得懂。

提交记录。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 2, mod = 1e9 + 7;
namespace martix {
    void mul(int ANS[][N], int x[][N], int y[][N])
    {
        int ans[N][N] = {};
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                for (int k = 0; k < N; k++)
                    ans[i][j] = (ans[i][j] + 1ll * x[i][k] * y[k][j]) % mod;
        memcpy(ANS, ans, sizeof ans);
    }
    void ksm(int f[][N], int A[][N], long long y)
    {
        while (y)
        {
            if (y & 1) mul(f, f, A);
            mul(A, A, A);
            y >>= 1;
        }
    }
}; using namespace martix;

void solve()
{
    long long n, ans = 0;
    cin >> n;
    int zltAK[N][N] = {1, 0}; //第一位填1 的 初始矩阵
    int ioi[N][N] = {
        0, 1, 
        1, 1
    };
    ksm(zltAK, ioi, n - 1), ans = (ans + zltAK[0][1]) % mod; //则最后一位只能填2

    int hxyAK[N][N] = {0, 1}; //第一位填2 的 初始矩阵
    int csp[N][N] = {
        0, 1, 
        1, 1
    };
    ksm(hxyAK, csp, n - 1), ans = (ans + hxyAK[0][0] + hxyAK[0][1]) % mod; //则最后一位可以填1或2

    cout << ans << '\n';
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

码字不易，希望能帮助到大家！