洛谷 P1939 矩阵加速（数列）

题意

a[1]=a[2]=a[3]=1
a[x]=a[x-3]+a[x-1] (x>3)
求a数列的第n项对1000000007取余的值。

题解

矩阵加速
设
$
F = \begin{bmatrix}
1 & 2 & 3 \
4 & 5 & 6 \
7 & 8 & 9
\end{bmatrix}
$

代码

#include <cstdio>
#include <algorithm>
#define REG(i, u, op) for (register int i = h[u][op]; i; i = e[i][op].nxt)
struct Edge
{
    int to, nxt;
}e[300000][2];
int n, k, u, v, ans;
int cnt[2], h[100000][2];
int f[100000], fa[100000], ff[100000];
inline void add_edge(const int& u, const int& v, const bool& op)
{
    e[++cnt[op]][op].to = v;
    e[cnt[op]][op].nxt = h[u][op];
    h[u][op] = cnt[op];
}
int find(const int& x) {return fa[x] ^ x ? fa[x] = find(fa[x]) : x; }
inline void add(const int& u, const int& v, const int& lca)
{
    ++f[u];
    ++f[v];
    --f[lca];
    --f[ff[lca]];
}
void dfs1(const int& x)
{
    fa[x] = x;
    REG(i, x, 1) if (fa[e[i][1].to])
        add(e[i][1].to, x, find(e[i][1].to));
    REG(i, x, 0) if (!fa[e[i][0].to])
    {
        ff[e[i][0].to] = x;
        dfs1(e[i][0].to);
        fa[e[i][0].to] = x;
    }
}
int dfs2(const int& x)
{
    int s = f[x];
    REG(i, x, 0) if (e[i][0].to ^ ff[x])
        s += dfs2(e[i][0].to);
    ans = std::max(ans, s);
    return s;
}
int main()
{
    scanf("%d%d", &n, &k);
    for (register int i = 1; i < n; ++i)
    {
        scanf("%d%d", &u, &v);
        add_edge(u, v, 0);
        add_edge(v, u, 0);
    }
    for (register int i = 1; i <= k; ++i)
    {
        scanf("%d%d", &u, &v);
        add_edge(u, v, 1);
        add_edge(v, u, 1);
    }
    dfs1(1);
    dfs2(1);
    printf("%d\n", ans);
}

洛谷 P1939 矩阵加速（数列）

原文：https://www.cnblogs.com/xuyixuan/p/9800426.html