[心之碎片] - 20240816模拟赛

柿子饼同学

总结与反思

ll = 1ll * int * int
取模要看好了, 不要把 ans 也乘了
一定要会打部分分!

A - 考虑条件的限制有什么巧方法水过去, 而不是一来就想高级算法

B - 中缀表达式求值要会

C - EXgcd 要更熟练一点

D - 计数题一定要有组合思想, 分类要细致, dfs 相关(做差, 栈, 树上差分) 之类的简单算法要先想, 树上路径其实是点

P7229 [COCI2015-2016#3] SLON
B 的 dfs 求中缀表达式

int dfs() {
    int res = 0, cur = 1, temp = 0;

    for (; s[pos] != ')' && s[pos]; pos++) {
        if (s[pos] == '(') {
            pos++;
            temp = dfs();
        } else if (isdigit(s[pos]) || s[pos] == 'x') {
            temp = temp * 10 + mp[s[pos]];
            temp %= m;
        } else {
            cur = 1ll * cur * temp % m;
            temp = 0;

            if (s[pos] != '*')
                res = (res + cur + m) % m;
            if (s[pos] == '-')
                cur = -1;
            if (s[pos] == '+')
                cur = 1;
        }
    }

    cur = 1ll * cur * temp % m;
    return (res + cur + m) % m;
}

C - P4031 [Code+#2] 可做题2
没啥可说的, 之前想的是枚举最后的 [l, r], 后来发现可以数论分块...

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll T, a1, l, r, k, p, m;

struct Matrix {
    ll mat[2][2];

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

    Matrix operator*(const Matrix& t) const {
        Matrix temp;
        for (int k = 0; k < 2; k++) {
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    temp.mat[i][j] += mat[i][k] * t.mat[k][j] % p;
                    temp.mat[i][j] %= p;
                }
            }
        }
        return temp;
    }
} base;

ll Exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }

    ll x1, y1;
    ll d = Exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;

    return d;
}

Matrix qp(Matrix a, ll b) {
    Matrix res;
    for (int i = 0; i < 2; i++) res.mat[i][i] = 1;

    while (b) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }

    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    freopen("fib.in", "r", stdin);
    freopen("fib.out", "w", stdout);

    base.mat[0][0] = base.mat[0][1] = base.mat[1][0] = 1;

    cin >> T;
    while (T--) {
        cin >> a1 >> l >> r >> k >> p >> m;

        a1 %= p;
        auto cur = qp(base, k - 1);

        ll ka1 = a1 * cur.mat[1][1] % p;
        ll ka2 = cur.mat[0][1] % p;
        ll gcd = __gcd(ka2, p);

        // ak = ka1 + ka2*a2
        // 得到不定方程:
        // ka2*x + p*y = m - ka1
        // A*x + B*y = C

        if ((m - ka1) % gcd) {
            cout << "0\n";
            continue;
        }

        ll A = ka2 / gcd, B = p / gcd, C = (m - ka1) / gcd;
        ll x, y, d;

        d = Exgcd(A, B, x, y);

        x = (x * C % B + B) % B;
        // x 是最小正整数解, x*a2 + ka1 = ak

        if (x > r) {
            cout << "0\n";
        } else {
            if (l <= x) {
                cout << (r - x) / B + 1 << '\n';
            } else {
                cout << (r - x) / B - (l - 1 - x) / B << '\n';
            }
        }
    }

    return 0;
}

D - 树上路径交
知知有一棵n个节点的树，根节点为1，树上每条边长度为1，定义G路径是连接祖先节点和其子孙节点的路径。
她想要知道有多少对路径的路径交是长度在 [L, R] 之间的G路径。

首先想到枚举交的部分, 然后一上一下每个点求一个不在同一个子树里取两个点的方案数
然后这里相当于利用 dfs 栈批量处理了

typedef long long ll;

const int N = 3e6 + 5;
const ll P = 1e9 + 7;

int n, l, r;
// up[i], 除了 i 这个子树和她的父节点, 在剩余子树中选择两个点使得不在同一个子树的方案数
// dn[i], i 这个子树, 选择 2 个点使得不在同一子树的方案数(不包括 i)
ll up[N], dn[N], dep[N], siz[N], ans;
vector<int> e[N];

void dfs0(int u) {
    siz[u] = 1;

    for (auto v : e[u]) {
        dfs0(v);
        siz[u] += siz[v];
    }

    ll temp = 1ll * n * (n - 1) / 2;
    dn[u] = 1ll * siz[u] * (siz[u] - 1) / 2;

    for (auto v : e[u]) {
        // 强制减去两个点都在 v 子树的方案
        dn[u] -= siz[v] * (siz[v] - 1) / 2;
        temp -= siz[v] * (siz[v] - 1) / 2;
    }

    dn[u] %= P;
    temp -= (n - siz[u]) * (n - siz[u] - 1) / 2;

    for (auto v : e[u]) {
        // 上面已经减过重复情况了, 这里只需要减掉一个点在 v 子树内的方案数
        up[v] = temp - (n - siz[v]) * siz[v];
    }
}

ll stk[N];
int top;

void dfs(int u) {
    if (u != 1) {
        top++;
        stk[top] = (stk[top - 1] + up[u]) % P;

        if (top >= l) {
            // sum 是指这一区间内的点上方选取 2 个不在同子树的点的方案数
            ll sum = ((stk[top - l + 1] - stk[max(0, top - r)]) % P + P) % P;

            // u 的子节点和这些点的上方节点, *2 是因为有 2 种情况, a, b -- c, d , a 可以选 c 也可以选 d
            ans = (ans + 2 * sum % P * dn[u] % P) % P;

            // u 的子节点和这些点(相同结尾 都是在这个区间内的点)
            ans = (ans + (min(top, r) - l + 1) * dn[u] % P) % P;

            // u 自己和这些点(相同起点 u)
            ans = (ans + sum) % P;
        }
    }

    for (auto v : e[u]) {
        dfs(v);
    }

    if (u != 1) {
        top--;
    }
}

某一个“天”

加油

简柠啦

很cool的阳

shuaijun

希儿的

日常膜拜

shuaijun

曾热爱这世界

👌

zsy0226

膜拜日常/orz

trinityee

我看的是高手成长阶梯啊！

森林格格屋

谢谢

啵啵虎0506

good