贪心 + 笛卡尔树，主席树 + 标记永久化，推式子 + 矩阵乘法

啥都不会，只会骗分 QwQ，没有想到的是 T2 $O(n^2)$ 预处理， $O(m \log n)$ 查询能得 90pts，T3 __int128 竟然存的下 $f_{30}$ ！充分告诉我们要有信仰 qaq

# A. 「2017 山东二轮集训 Day1」第二题

看起来是这套题里面最简单的了。

大力贪心。

每次找到最低点，然后分治处理两边。

答案分别加上两边的大小除以 $k$ ，然后多余的部分送给最低点统计。

可以通过建笛卡尔树找最低点。

#include <bits/stdc++.h>
#define int long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 10;
int n, k;
int h[N];

#define ls t[x].l
#define rs t[x].r
struct Tree{
    int l, r;
}t[N];
int stk[N], top, res;
int rt, ans;
int sum[N], siz[N];

inline void dfs(int x, int fa){
    siz[x] = 1;
    if(ls) dfs(ls, x), sum[x] += sum[ls], siz[x] += siz[ls];
    if(rs) dfs(rs, x), sum[x] += sum[rs], siz[x] += siz[rs];
    sum[x] += siz[x] * (h[x] - h[fa]);
    if(sum[x] > 0){
        int tot = ceil(1.0 * sum[x] / k);
        ans += tot, sum[x] -= tot * k;
    }
}

signed main(){
    n = read(), k = read();
    for(int i = 1; i <= n; ++i) h[i] = read();
    for(int i = 1; i <= n; ++i, res = 0){
        while(top && h[stk[top]] > h[i]) res = stk[top--];
        t[i].l = res, t[stk[top]].r = i, stk[++top] = i;
    }
    rt = stk[1];
    dfs(rt, 0);
    write(ans), puts("");
    return 0;
}
// X.K.

# B. 「2017 山东二轮集训 Day1」第一题

毒瘤数据结构。

大致思路是找出每个点向右能到达的最远的点，然后把这个贡献加到主席树里，查询的时候直接在主席树上查询 $l \sim r$ 的区间和即可。

那么如何预处理呢？

设 $s[0/1][i][j]$ 为前 $i$ 个数的异或和，最高位 $j$ 从 $1 \rightarrow 0$ 和 $0 \rightarrow 1$ 的个数， $sum_i$ 为前缀异或和。

对于区间 $l \sim r$ ，如果 $sum_{l - 1}$ 的最高位 $j$ 为 1，那么 $l \sim r$ 中第 $j$ 位就不能出现 $1 \rightarrow 0$ ，反之不能出现 $0 \rightarrow 1$ 。

所以可以使用二分查找。

然后在主席树进行区间加，这需要使用标记永久化。

所谓标记永久化其实就是修改时不写 $\text{pushdown}$ ，只在查询的时候加上标记的贡献即可。

#include <bits/stdc++.h>
#define ll long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e5 + 10;
int n, m, lst;
int a[N], pos[N], sum[N];
int s[2][N][66];

inline int highbit(int x){
    for(int i = 30; i >= 0; --i) if((x >> i) & 1) return i;
    return -1;
}
inline int bit(int x, int y) {return (x >> y) & 1;}

inline bool check(int l, int r){
    for(int i = 30; i >= 0; --i){
        int x = !bit(sum[l - 1], i);
        if(s[x][r][i] - s[x][l - 1][i] > 0) return 0;
    }
    return 1;
}

inline int find(int x){
    int l = x, r = n, res = x;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(x, mid)) res = mid, l = mid + 1;
        else r = mid - 1;
    }
    return res;
}

#define ls(x) t[x].l
#define rs(x) t[x].r
int rt[N], cnt;
struct Tree{
    int val, tag, l, r;
}t[N << 5];

inline int build(int l, int r){
    int p = ++cnt;
    if(l == r) return p;
    int mid = (l + r) >> 1;
    ls(p) = build(l, mid), rs(p) = build(mid + 1, r);
    return p;
}

inline int update(int pre, int L, int R, int k, int l, int r){
    int p = ++cnt;
    t[p] = t[pre];
    if(L == l && R == r) return t[p].tag += k, p;
    t[p].val += k * (R - L + 1);
    int mid = (l + r) >> 1;
    if(L <= mid) ls(p) = update(ls(pre), L, min(R, mid), k, l, mid);
    if(R > mid) rs(p) = update(rs(pre), max(L, mid + 1), R, k, mid + 1, r);
    return p;
}

inline int query(int x, int y, int L, int R, int l, int r){
    int res = (t[y].tag - t[x].tag) * (R - L + 1);
    if(L == l && R == r) return res + t[y].val - t[x].val;
    int mid = (l + r) >> 1;
    if(L <= mid) res += query(ls(x), ls(y), L, min(R, mid), l, mid);
    if(R > mid) res += query(rs(x), rs(y), max(L, mid + 1), R, mid + 1, r);
    return res;
}

signed main(){
    n = read();
    for(int i = 1; i <= n; ++i){
        sum[i] = sum[i - 1] ^ (a[i] = read());
        for(int j = 0; j <= 30; ++j) s[0][i][j] = s[0][i - 1][j], s[1][i][j] = s[1][i - 1][j];
        int j = highbit(a[i]);
        if(~j) s[bit(sum[i - 1], j)][i][j]++;
    }
    for(int i = 1; i <= n; ++i) pos[i] = find(i);
    rt[0] = build(1, n);
    for(int i = 1; i <= n; ++i) rt[i] = update(rt[i - 1], i, pos[i], 1, 1, n);
    m = read();
    while(m--){
        int l = (read() + lst) % n + 1, r = (read() + lst) % n + 1;
        if(l > r) swap(l, r);
        write(lst = query(rt[l - 1], rt[r], l, r, 1, n)), puts("");
    }
    return 0;
}
// X.K.

# C. GCD

这道题就相当之困难了。

题目让我们求 $\gcd(af_n + bf_{n + 1}, cf_n + df_{n + 1})$ 。

首先通过更相减损术可以去掉 $df_{n + 1}$ 这一项。

式子就变成了 $\gcd(a'f_n + b'f_{n + 1}, c'f_n)$ 。

我们把 $c'$ 和 $f_n$ 分开计算：

$\gcd(af_n + bf_{n + 1}, f_n) = \gcd(bf_{n + 1}, f_n)$ 。

通过打表发现， $\gcd(f_n, f_{n + 1}) = 3^{\frac n2}$ ，所以就是 $\gcd(b, f_n) \times 3^{\frac n2}$ 。
$\gcd(af_n + bf_{n + 1}, c)$ ，设 $g = \gcd(af_n + bf_{n + 1}, f_n)$ ，然后先除掉这一部分，即求 $\gcd(\frac {af_n + bf_{n + 1}}g, c)$ ，然后让左边模 $gc$ 计算即可。

所以答案就是：

$\gcd(\frac {af_n + bf_{n + 1} \bmod gc}g, c) \times g \times 3^{\frac n2} \bmod p$

#include <bits/stdc++.h>
#define int long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e6;
int T, n, p, a, b, c, d;
int mod = 998244353;

struct Matrix{
    int num[2][2];

    Matrix (){memset(num, 0, sizeof(num));}
    inline void init (){num[0][0] = num[0][1] = 1;}

    Matrix operator / (int b) const{
        Matrix r;
        for(int i = 0; i < 2; ++i)
            r.num[i][0] = num[i][0] / b, r.num[i][1] = num[i][1] / b;
        return r;
    }

    Matrix operator * (const Matrix &b) const{
        Matrix r;
        for(int i = 0; i < 2; ++i)
            for(int j = 0; j < 2; ++j)
                r.num[i][j] = (num[i][0] * b.num[0][j] % mod + num[i][1] * b.num[1][j] % mod) % mod;
        return r;
    }

    Matrix operator ^ (int b) const{
        Matrix a, r;
        memcpy(a.num, num, sizeof(num));
        r.num[0][0] = r.num[1][1] = 1;
        for(; b; a = a * a, b >>= 1)
            if(b & 1) r = r * a;
        return r;
    }
}X, X2;

inline int gcd(int a, int b){
    return !b ? a : gcd(b, a % b);
}

inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = res * a % p;
        a = a * a % p, b >>= 1;
    }
    return res;
}

int t;

inline int f(int n, int p){
    if(n <= 1) return 1;
    n--, mod = p;
    Matrix F;
    F.init();
    F = F * (X2 ^ t);
    n -= (t << 1);
    if(n < 0) return F.num[0][1];
    if(n > 0) F = F * X;
    return F.num[0][0];
}

inline int solve(){
    n = read(), p = read(), a = read(), b = read(), c = read(), d = read();
    while(d){
        int k = b / d;
        b -= k * d, a -= k * c;
        swap(a, c), swap(b, d);
    }
    t = n >> 1, mod = p;
    int tmp = qpow(3, t);
    if(!c) return (a * f(n, p) % p + b * f(n + 1, p) % p) % p * tmp % p;
    if(!b) return gcd(a, c) % p * f(n, p) % p * tmp % p;
    int g = gcd(f(n, b), b);
    mod = g * c;
    return gcd((a * f(n, mod) % mod + b * f(n + 1, mod) % mod) % mod / g, c) * g % p * tmp % p;
}

signed main(){
    X.num[0][0] = 9, X.num[0][1] = 1, X.num[1][0] = 12;
    X2 = X * X / 3;
    T = read();
    while(T--) write(solve()), puts("");
    return 0;
}
// X.K.

# A. 「2017 山东二轮集训 Day1」第二题

# B. 「2017 山东二轮集训 Day1」第一题

# C. GCD

P2757 [国家集训队]等差子序列 题解

20220305

P2757 [国家集训队]等差子序列题解