A – 小L的数列

这道题的式子跟 Codeforces 一道 F 题是一样的，让我误以为是 BSGS 之类的玩意，最后发现其实算是矩阵乘法的题。

考虑任意一个答案都是由\(\{f_n\}\)的幂的积组成的，由于\(k\)很小，所以我们可以考虑计算每一个\(f\)的指数，然后就可以用快速幂来计算这些东西。

我们可以来推一下矩阵。考虑一个\(k \times k\)大小的矩阵，然后第\(k\)列的第\(i\)行为\(f_i\)的指数。然后写一些约束条件：

\[ A[i][k] = \sum_{s = 1}^k A'[i][s] \times A'[s][k] \]

思考后发现，每一个指数都来源于\(i – 1\)，且：

\[ \begin{bmatrix} b_3 \\ b_2 \\ b_1 \end{bmatrix} \to \begin{bmatrix} b_1 b_3 \\ b_1 b_2 + b_1 \\ b_1^2 + b_2 \end{bmatrix} \]

发现第\(i\)行是乘上一个\(b_1\)再加上\(b_{i – 1}\)。那么：

\[ A[i][k] = A'[i][k] \times b_1 + b_{i – 1} \]

我们来尽量配凑这个矩阵中的系数：\( A'[k][k] = b_1, A'[i][i – 1] = 1 \)。

然后就可以愉快的写代码了。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 40000010, mod1 = 998244353, mod2 = 998244352;

int n, k, f[MAX_N];

int quick_pow(int bas, int tim, int mod)
{
    int ans = 1;
    bas %= mod;
    while (tim)
    {
        if (tim & 1)
            ans = 1LL * ans * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}

struct matrix
{
    int mat[201][201];

    matrix() { memset(mat, 0, sizeof(mat)); }

    matrix operator*(const matrix &target)
    {
        matrix ans;
        for (int i = 1; i <= k; i++)
            for (int j = 1; j <= k; j++)
                for (int s = 1; s <= k; s++)
                    ans.mat[i][j] = (1LL * ans.mat[i][j] + 1LL * mat[i][s] * target.mat[s][j] % mod2) % mod2;
        return ans;
    }

    matrix operator^(const int &ti)
    {
        int tim = ti;
        matrix ans, bas = *this;
        for (int i = 1; i <= k; i++)
            ans.mat[i][i] = 1;
        while (tim)
        {
            if (tim & 1)
                ans = ans * bas;
            bas = bas * bas;
            tim >>= 1;
        }
        return ans;
    }
} A;

int main()
{
    /*
	freopen("seq.in", "r", stdin);
	freopen("seq.out", "w", stdout);
    */
    scanf("%d%d", &n, &k);
    for (int i = 2; i <= k; i++)
        A.mat[i][i - 1] = 1;
    for (int i = k; i >= 1; i--)
        scanf("%d", &A.mat[i][k]);
    for (int i = 1; i <= k; i++)
        scanf("%d", &f[i]);
    if (n <= k)
        printf("%d", f[n] % mod1), exit(0);
    n -= k;
    A = A ^ n;
    int ans = 1;
    for (int i = 1; i <= k; i++)
        ans = 1LL * ans * quick_pow(f[i], A.mat[i][k], mod1) % mod1;
    printf("%d", ans);
    return 0;
}

B – 梦境

考虑直接贪心。枚举转折点\(p_i\)，让所有左端点小于\(p_i\)的区间全部加入优先队列，然后再推出右端点小于\(p_i\)的，那么优先队列就是答案集合，那么可以贪心地取右端点最近的点进行配对。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 2000;

int n, m, pts[MAX_N];
struct interval
{
    int l, r;
    bool operator<(const interval &target) const { return l < target.l || (l == target.l && r < target.r); }
} ints[MAX_N];

struct compare
{
    bool operator()(interval a, interval b) { return a.r > b.r || (a.r == b.r && a.l > b.l); }
};

priority_queue<interval, vector<interval>, compare> q;

int main()
{
    /*
    freopen("dream.in", "r", stdin);
	freopen("dream.out", "w", stdout);
    */
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &ints[i].l, &ints[i].r);
    for (int i = 1; i <= m; i++)
        scanf("%d", &pts[i]);
    sort(ints + 1, ints + 1 + m);
    sort(pts + 1, pts + 1 + m);
    int ans = 0;
    for (int i = 1, cur = 1; i <= m; i++)
    {
        int u = pts[i];
        while (cur <= n && ints[cur].l <= u)
            q.push(ints[cur++]);
        while (!q.empty() && q.top().r < u)
            q.pop();
        if (!q.empty())
            ans++, q.pop();
    }
    printf("%d\n", ans);
    return 0;
}

C – 树

这道题就很厉害了。

考虑计算非法的对数，然后间接求合法对数。我们发现，对于一个点对\((x, y)\)，不合法数量有两种情况：

• \(lca(x, y) != x, lca(x, y) != y\)时，不合法数量就是\(size[x] \times size[y]\)。
• \(lca(x, y) = x\)时，不合法数量就是\(size[y] \times (tot – size[x] + 1)\)。

这两个都比较像二元乘积，考虑抽象成矩形面积，会发现其实就是把\(x\)的 DFS 序作为\(x\)轴，\(y\)的 DFS 序作为\(y\)轴，然后放置一个或者两个矩形。所以，可以知道，这就是一道扫描线的题目。

// C.cpp
#include <bits/stdc++.h>
#define ll long long
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

using namespace std;

const int MAX_N = 1e5 + 200;

int n, m, current, head[MAX_N], dfn[MAX_N], low[MAX_N], tot, rectot;
int fa[20][MAX_N], dep[MAX_N];
ll tree[MAX_N << 8], tag[MAX_N << 8];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

struct line_node
{
    int x, y1, y2, aff;
    bool operator<(const line_node &ln) const { return x < ln.x; }
} nodes[MAX_N << 2];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void dfs(int u)
{
    dfn[u] = ++tot, dep[u] = dep[fa[0][u]] + 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa[0][u])
            fa[0][edges[i].to] = u, dfs(edges[i].to);
    low[u] = tot;
}

void update(int ql, int qr, int l, int r, int p, ll val)
{
    if (ql <= l && r <= qr)
    {
        tag[p] += val;
        if (tag[p])
            tree[p] = r - l + 1;
        else if (l == r)
            tree[p] = 0;
        else
            tree[p] = tree[lson] + tree[rson];
        return;
    }
    if (ql <= mid)
        update(ql, qr, l, mid, lson, val);
    if (mid < qr)
        update(ql, qr, mid + 1, r, rson, val);
    if (tag[p])
        tree[p] = r - l + 1;
    else if (l == r)
        tree[p] = 0;
    else
        tree[p] = tree[lson] + tree[rson];
}

void create_rectangle(int x1, int x2, int y1, int y2)
{
    nodes[++rectot] = line_node{x1, y1, y2, 1};
    nodes[++rectot] = line_node{x2 + 1, y1, y2, -1};
}

int lca(int x, int y)
{
    for (int i = 19; i >= 0; i--)
        if (dep[fa[i][y]] > dep[x])
            y = fa[i][y];
    return y;
}

void process_pair()
{
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (dfn[x] > dfn[y])
            swap(x, y);
        if (dfn[x] < dfn[y] && dfn[y] <= low[x])
        {
            int son = lca(x, y);
            if (dfn[son] > 1)
                create_rectangle(1, dfn[son] - 1, dfn[y], low[y]);
            if (low[son] < n)
                create_rectangle(dfn[y], low[y], low[son] + 1, n);
        }
        else
            create_rectangle(dfn[x], low[x], dfn[y], low[y]);
    }
    sort(nodes + 1, nodes + 1 + rectot);
    long long answer = 1LL * n * (n - 1) / 2;
    for (int i = 1, cur = 1; i <= n; i++)
    {
        while (cur <= rectot && nodes[cur].x <= i)
            update(nodes[cur].y1, nodes[cur].y2, 1, n, 1, nodes[cur].aff), cur++;
        answer -= tree[1];
    }
    printf("%lld", answer);
}

int main()
{
    /*
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
    */
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= n - 1; i++)
        scanf("%d%d", &x, &y), addpath(x, y), addpath(y, x);
    dfs(1);
    for (int i = 1; i < 20; i++)
        for (int j = 1; j <= n; j++)
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
    process_pair();
    return 0;
}