首页 模拟赛

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

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

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

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

大力贪心。

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

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

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

#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∼rl \sim r 的区间和即可。
那么如何预处理呢？
设 s[0/1][i][j]s[0/1][i][j] 为前 ii 个数的异或和，最高位 jj 从 1→01 \rightarrow 0 和 0→10 \rightarrow 1 的个数，sumisum_i 为前缀异或和。
对于区间 l∼rl \sim r，如果 suml−1sum_{l - 1} 的最高位 jj 为 1，那么 l∼rl \sim r 中第 jj 位就不能出现 1→01 \rightarrow 0，反之不能出现 0→10 \rightarrow 1。
所以可以使用二分查找。
然后在主席树进行区间加，这需要使用标记永久化。
所谓标记永久化其实就是修改时不写 pushdown\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⁡(afn+bfn+1,cfn+dfn+1)\gcd(af_n + bf_{n + 1}, cf_n + df_{n + 1})。
首先通过更相减损术可以去掉 dfn+1df_{n + 1} 这一项。
式子就变成了 gcd⁡(a′fn+b′fn+1,c′fn)\gcd(a'f_n + b'f_{n + 1}, c'f_n)。
我们把 c′c' 和 fnf_n 分开计算：
  • gcd⁡(afn+bfn+1,fn)=gcd⁡(bfn+1,fn)\gcd(af_n + bf_{n + 1}, f_n) = \gcd(bf_{n + 1}, f_n)。
    通过打表发现，gcd⁡(fn,fn+1)=3n2\gcd(f_n, f_{n + 1}) = 3^{\frac n2}，所以就是 gcd⁡(b,fn)×3n2\gcd(b, f_n) \times 3^{\frac n2}。
  • gcd⁡(afn+bfn+1,c)\gcd(af_n + bf_{n + 1}, c)，设 g=gcd⁡(afn+bfn+1,fn)g = \gcd(af_n + bf_{n + 1}, f_n)，然后先除掉这一部分，即求 gcd⁡(afn+bfn+1g,c)\gcd(\frac {af_n + bf_{n + 1}}g, c)，然后让左边模 gcgc 计算即可。
所以答案就是：
gcd⁡(afn+bfn+1modgcg,c)×g×3n2modp\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.
 更新于   阅读次数  次