9.11

A

给定 $n$ 和 $k$，求出有多少长度为 $2n$ 的序列 $A(a_1,a_2,a_3\cdots a_{2n})$ 满足以下条件 ：

  1. $A$ 包含 $n$ 个 $+1$ 和 $n$ 个 $−1$
  2. 有且仅有 $k$ 对 $(l,r)$ 满足 $(1\le l\le r)$ 且 $\left(\sum_{i=l}^ra_i\right)=0$

$1 \le n \le 30, 1 \le k \le n^2$

计算序列的前缀和 $S$ ，然后我们发现前缀和的形态就像是一棵树 ：

我们自顶向下构造这棵树，每次加一层。

令 f[len][cnt][hole] 为 目前构造了长度为 len 的序列， 有 cnt个和为 $0$ 的区间，中间有hole 个“洞”（就是还没填满的部分）

转移就可以 f[len+x][cnt+C(x,2)][x-(hole+2)] += f[len][cnt][hole] 了！

由于有 $n^4$ 个状态，每次转移是 $O(n)$ 的，所以总复杂度就是 $O(n^5)$ 的！

填好了表格之后答案为 f[2n+1][k][0] + sum{ f[i][j][k] * f[2n+1-i][k-j][k-1] }（要考虑和为负数的情况，此时把两棵树“拼”起来即可）

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
typedef long long ll;
 
int n,k;
ll C[35][35];
ll dp[70][40][902];
 
int C_2(int x)
{
    return x * (x-1) >> 1;
}
 
void main()
{
    ios :: sync_with_stdio(false);
    cin >> n >> k;
    for(int i = 0;i <= n+1;i++)
    {
        C[i][0] = 1;
        for(int j = 1;j<=i;j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
     
    for(int x = 0;x <= n+1;x++)
        if(C_2(x) <= k) dp[x][x][C_2(x)] = 1;
     
    for(int c = 0;c <= k;c++)
    for(int i = 1;i <= (n << 1 | 1);i++)
    for(int j = 1;j <= min(n+1,i);j++)
    if(dp[i][j][c])
    for(ll x = j + 1;x <= n + 1;x++)
    {
        int c2 = c + C_2(x);
        if(c2 > k || i + x > (n << 1 | 1)) continue;
        dp[i + x][x - j][c2] += C[x-1][j] * dp[i][j][c];
    }
    ll ans = 0;
    for(int j = 1;j <= n+1;j++)
    for(int i = 0;i <= (n << 1 | 1);i++)
    {
        int ii = (n << 1 | 1)- i;
        int jj = j-1;
        for(int c = 0;c <= k;c++)
        ans += dp[i][j][c] * dp[ii][jj][k-c];
    }
    cout << ans;
    return;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

B

有一个长度为 $2n$ 的环 $A(A_1,A_2,\cdots A_{2n})$。

有 $2n$ 个人，第 $i$ 个人有一个数字 $B_i$ ，意思是他要求 $\left(\sum_{i}^{i+n-1} A_i\right)\ge B_i$ 。（对于 $i>2n$ 的情况 $A_i=A_{i-2n}$ ）。

在满足所有人的要求的情况下，请求 出 $\min(\sum A_i)$ （把 AA 的和最小化）

$1 \le n \le 1.5 \times 10^5 , 0 \le A_i \le 5 \times 10^8$

我们考虑对序列 $a$ 求个前缀和记为 $S$ （怎么又是前缀和） ，令 $X = S_{2n}$

容易发现 $X$ 具有单调性(当一个 $X$ 的值符合条件之后更大的值也一定符合条件)。

对于第 $i$ 个人 $(i \le n)$ ，他的要求可以记为 ： $b_i \le S_{i + n - 1} - S_{i-1}$

对于第 $i$ 个人 $(i > n)$ ，他的要求可以记为 ： $X - b_i \ge S_{i-1} - S_{i - n} $

综合起来，令 $L_i = b_i, R_i = X - b_{i+n} (1\le i \le n)$，则 $a$ 应该满足

$L_i \le S_{i+n-1} - S_{i-1} \le R_i (1 \le i \le n)$

同时 $S_n$ 越大，那么 $S_{2n-1}$ 和 $S_{n-1}$ 越大。

最后我们需要判定是否存在一个 $S_n$ 使得 $S_{n-1} \le S_n $ 且 $S_{2n-1} \le X$

我们可以二分 $S_n$ ，然后可以以 $O(n \log^2 A_i)$ 的复杂度解决了这道题（

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 300010 
typedef long long ll;
 
int n;
int a[N];
int L[N],R[N];
 
bool check(int );
 
void main()
{
    ios :: sync_with_stdio(false);
    cin >> n;
    for(int i = 0;i<(n << 1);i++) cin >> a[i];
     
    int l = 0,r = 1e9;
    while(l < r)
    { 
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
    return;
}
 
bool check(int x)
{
    for(int i = 0;i < n;i++)
    if(a[i] + a[i + n] > x)
        return false;
    L[n] = a[0];
    for(int i = 1;i < n;i++)
        L[i] = max(L[i-1],L[i + n - 1] + a[i + n] - x),
        L[i + n] = max(L[i + n - 1],L[i - 1] + a[i]);
    int p = L[n - 1];L[n] = max(L[n],p);
    if(L[n] > x - a[n]) return false;
    for(int i = 1;i < n;i++)
        L[i] = max(L[i-1],L[i + n - 1] + a[i + n] - x),
        L[i + n] = max(L[i + n - 1],L[i - 1] + a[i]);
    if(p != L[n - 1]) return false;
    return (x >= L[2 * n - 1]);
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

C

请写一种数据结构，维护二维点集（可能重复）支持以下三种操作：

  1. add x y 添加一个点 $(x,y)$
  2. remove x y 删除（保证存在） $(x,y)$
  3. find x y 查询 $(x’,y’)$ 满足 $x’>x,y’>y$ ，如有多个取 $x$ 最小的，如仍有多个取 $y$ 最小的。

$n$ 次操作，

$1 \le n \le 2\times 10^5$ ，$0\le x,y \le 10^9$

首先把 $x$ 离散化。

这样我们就可以把所有 $x$ 值放到一颗值域线段树上了

对于相同的 $x$ 不同的 $y$ 用 std::set 来维护

查询就线段树二分。复杂度 $O(nlogn)$ ，离线。

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 200010
struct node{
    int x,y;
    node(){}
    node(int _x,int _y) : x(_x),y(_y){}
    friend bool operator < (node a,node b)
    {
        return a.x != b.x ? a.x < b.x : a.y < b.y;
    }
};
struct query{
    int x,y;
    int type; // 1 -> add,2 -> del, 3 -> find. 
}q[N];
struct Tree
{
    int l,r;
    int maxx;
    #define ls(x) (x << 1)
    #define rs(x) (x << 1 | 1)
}t[N << 2];
int X[N],top;
multiset<int> awa[N << 2];
 
int n;
int tot;
string opt;
 
void push_up(int x)
{
    t[x].maxx = max(t[ls(x)].maxx,t[rs(x)].maxx);
}
 
void build(int x,int l,int r)
{
    if(l == r)
    {
        t[x].l = X[l];
        t[x].r = X[l];
        t[x].maxx = -1;
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
    t[x].l = t[ls(x)].l,t[x].r = t[rs(x)].r;
    push_up(x);
}
 
void insert(int x,int y,int k,int l = 1,int r = tot,int p = 1)
{
    if(l == r)
    {
        if(k)
        {
            awa[p].insert(y);
            t[p].maxx = max(t[p].maxx,y);
        }
        else
        {
            awa[p].erase(y);
            if(awa[p].empty()) t[p].maxx = -1;
            else t[p].maxx = *(--awa[p].end());
        }
        return;
    }
    int mid = (l + r) >> 1;
    if(x >= t[ls(p)].l && x <= t[ls(p)].r) insert(x,y,k,l,mid,ls(p));
    else insert(x,y,k,mid+1,r,rs(p));
    push_up(p);
}
 
node query(int x,int y,int l = 1,int r = tot,int p = 1)
{
    if(t[p].r < x) return node(-1,-1);
    if(l == r)
    {
        if(awa[p].empty()) return node(-1,-1);
        auto a = awa[p].upper_bound(y);
        if(a == awa[p].end()) return node(-1,-1);
        return node(t[p].l,*a);
    }
    int mid = (l + r) >> 1;
    node ans(-1,-1);
    if(t[ls(p)].maxx > y && t[ls(p)].r > x)
    ans = query(x,y,l,mid,ls(p));
    if(ans.x == -1 && t[rs(p)].maxx > y && t[rs(p)].r > x)
    ans = query(x,y,mid+1,r,rs(p));
    return ans;
}
 
void main()
{
    cin >> n;
    int x,y;
    for(int i = 1;i<=n;i++)
    {
        cin >> opt >> q[i].x >> q[i].y;
        if(opt[0] == 'a')
        {
            q[i].type = 1;
            X[++top] = q[i].x;
        }
        else if(opt[0] == 'r')
            q[i].type = 2;
        else
            q[i].type = 3;
    }
    if(!top) X[++top] = -1;
    sort(X+1,X+top+1);
    tot = unique(X,X+top+1) - X - 1;
    for(int i = tot + 1;i <= 2e5;i++) X[i] = -1;
    build(1,1,tot);
    for(int i = 1;i<=n;i++)
    {
        if(q[i].type == 1) insert(q[i].x,q[i].y,1);
        else if(q[i].type == 2) insert(q[i].x,q[i].y,0);
        else
        {
            node now = query(q[i].x,q[i].y);
            if(now.x == -1) cout << -1 << '\n';
            else cout << now.x << ' ' << now.y << '\n';
        }
    }
    return;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

9.12

A

给定一棵 $n$ 个点的树，每条边有个正整数边权。有 $q$ 次修改操作，每次会修改一条边的边权。

在所有修改之前以及每次修改后，你需要求出有多少个无序点对满足它们之间的最短路径上所有边权的最大公约数 $=1$。

第一行一个整数 $n$ ，接下来 $n−1$ 行每行三个整数 $a_i,b_i,c_i$ ，表示有一条连接 $a_i$ 和 $b_i$ ，边权为 $c_i$ 的边。

接下来一行一个整数 $q$，接下来 $q$ 行每行两个整数 $x_i,y_i$ ，表示将第 $x_i$ 条边的权值修改为 $y_i$

$1 \le n \le 10^5, 0 \le 1 \le 100,1 \le c_i ,y_i \le 10^6$

这竟然是一道莫反题

（幸亏这两天学了学莫反不然连题解都看不懂虽然依然看不懂）

原题解太简略，这里写一下式子 ：

设 $\gcd(i \sim j)$ 表示树上这两点之间边权的 $\gcd$

那么要求的就是 ：

考虑莫比乌斯反演，推一下经典式子 ：

于是变成统计 $k \mid \gcd$ 的点对数量。

对于每个边权，首先去掉重复的质因子，这样他的质因子 只有不超过 $c=7$ 个。

那么对于每个 $k$ ，将边权是 $k$ 的倍数的边取出，用并查集计算答案。

对于修改涉及的边，我们一开始不将他们加入并查集。

然后我们枚举 $q+1$ 个时刻，再将这些边加入，统计答案，再删去即可。

时间复杂度 $O(L + (n + q^2)2^c \log n)$\

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 100110
#define M 1000010
typedef long long ll;
const int mod = 998244353;
struct edge{
    int u,v;
    int w;
    void init()
    {cin >> u >> v >> w;}
}e[N];
int n,m;
bool vis[M];
int p[M],tot;
int mu[M],mn[M];
vector <int> g[M];
int pre[N],ltim[N],rtim[N];
int siz[N],fa[N],top;
pair<int ,int >stk[N];
ll cur,ans[110];
int num,tim[N << 2];
vector<int> seg[N << 2];
 
int find(int );
void back(int );
void euler(int );
void calc(int ,int );
void merge(int ,int );
void solve(int ,int ,int );
void push(int ,int ,int ,int ,int ,int );
 
void main()
{
    ios :: sync_with_stdio(false);
    euler(1e6);
    cin >> n;
    for(int i = 1;i < n;i++)
    e[i].init();
    cin >> m;
    for(int i = 1;i < n;i++) pre[i] = i,ltim[i] = 0,rtim[i] = m;
    int x,y,c;
    for(int i = 1;i <= m;i++)
    {
        cin >> x >> y;
        c = n + i - 1;
        e[c] = e[x],e[c].w = y;
        rtim[pre[x]] = i - 1;
        ltim[pre[x] = c] = i;
        rtim[c] = m;
    }
    for(int i = 1;i<=n;i++) siz[i] = 1,fa[i] = i;
    for(int i = 1;i<=n + m - 1;i++) calc(e[i].w,i);
    for(int i = 1;i<=1e6;i++)
    if(g[i].size())
    {
        num = i;
        for(auto o : g[i]) push(1,0,m,ltim[o],rtim[o],o);
        solve(1,0,m);
    }
    for(int i = 1;i <= m;i++) ans[i] += ans[i-1];
    for(int i = 0;i <= m;i++) cout << ans[i] << '\n';
    return;
}
 
void solve(int p,int l,int r)
{
    if(tim[p] != num)
    {
        ans[l] += cur;
        ans[r + 1] -= cur;
        return;
    }
    int pre = top;
    for(auto i : seg[p]) merge(e[i].u,e[i].v);
    if(l == r) ans[l] += cur,ans[r + 1] -= cur;
    else{
        int mid = (l + r) >> 1;
        solve(p << 1,l,mid);
        solve(p << 1 | 1,mid + 1,r);
    }
    back(pre);
}
 
void push(int p,int l,int r,int L,int R,int o)
{
    if(tim[p] != num){
        seg[p].clear();
        tim[p] = num;
    }
    if(L <= l && r <= R) return seg[p].emplace_back(o),void();
    int mid = (l + r) >> 1;
    if(L <= mid) push(p << 1,l,mid,L,R,o);
    if(R > mid) push(p << 1 | 1,mid+1,r,L,R,o);
}
 
void back(int aim)
{
    while(top > aim)
    {
        int u = stk[top].first,v = stk[top--].second;
        siz[v] -= siz[u];fa[u] = u;
        cur -= 1ll * siz[u] * siz[v] * mu[num];
    }
}
 
void merge(int u,int v)
{
    u = find(u),v = find(v);
    if(u == v) return;
    if(siz[u] > siz[v]) swap(u,v);
    cur += 1ll * siz[u] * siz[v] * mu[num];
    fa[u] = v;siz[v] += siz[u];
    stk[++top] = make_pair(u,v);
}
 
int find(int x)
{
    return fa[x] == x ? x : find(fa[x]);
}
 
void calc(int v,int o)
{
    int cnt = 0,c[20];
    while(v > 1)
    {
        c[cnt++] = mn[v];int x = mn[v];
        while(v % x == 0) v /= x;
    }
    for(int i = 0;i < (1 << cnt);i++)
    {
        int s = 1;
        for(int j = 0;j < cnt;j++) if(i >> j & 1) s *= c[j];
        g[s].emplace_back(o);
    }
}
 
void euler(int n)
{
    mu[1] = 1;
    for(int i = 2;i<=n;i++)
    {
        if(!vis[i]) p[++tot] = i,mu[i] = -1,mn[i] = i;
        for(int j = 1;j<=tot && i * p[j] <= n;j++)
        {
            vis[i * p[j]] = 1;
            mn[i * p[j]] = p[j];
            if(i % p[j] == 0) break;
            mu[i * p[j]] = -mu[i];
        }
    }
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

B

输入三个整数 $L,R,V$ ，询问有多少对 $(l,r)$ 满足 $L \le l \le r \le R$ 且 $l\oplus(l+1)\oplus⋯\oplus r=Vl\oplus(l+1)\oplus \cdots \oplus r=V$

答案对 $998244353$ 取模

这里出现了我从未听说过的 “经典结论” ：

我们记 $w_k = 0 \oplus 1 \oplus \cdots \oplus (k−1) $
那么也就是 ：

我们想要计算满足 $L \le i < j \le R+1$ 并且 $w_i \oplus w_j = V$ 的数对 $(i,j)$

但是我们有了上边的经典结论，所以我们只要确定 $i$ 和 $j$ 模 $4$ 的余数，一共 $16$ 种情况，但是比较难处理的只有 $(0,0),(0,2),(2,0),(2,2)$ 四种情况，其余情况要么可以确定一个端点的位置，要么形如等差数列，均可快速求得。

这四种情况在本质上都是一样的，给定区间 $[l-1,r]$ ，从区间里抽取两个不相等的数 $a,b$ ，求 $a \oplus b = V$ 的对数。

可以用数位DP解决， f[i][2][2] 表示还有 $i$ 位，第一个数，第二个数是否卡上界的方案数，然后就做完了。

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
namespace Pozhu{
using namespace std;
typedef long long llt;
 
const int m[4]= {0,1,3,0};
const int mod = 998244353;
 
int f[66][2][2][2];
llt L, R, V, ans;
 
int main() {
    cin >> L >> R >> V; L--;
    for (int i = 0; i < 4; i++) 
    for (int j = 0; j < 4; j++) 
    if ((m[i] ^ m[j]) == (V & 3)) {
        memset(f, 0, sizeof f);
        f[1][(L & 3) <= i][i < j][j <= (R & 3)] = 1;
        for (int k = 2; k <=60; k++) 
        for (int a = 0; a <= 1; a++) 
        for (int b = 0; b <= 1; b++) 
        for (int c = 0; c <= 1; c++) 
        for (int x = 0; x <= 1; x++) 
        for (int y = 0; y <= 1; y++) 
        if((((i & 1) ? 0 : x) ^ ((j & 1) ? 0 : y)) == (V >> k & 1)) {
            int l = L >> k & 1;
            int r = R >> k & 1;
            f[k][l < x || l == x && a][x < y || x == y && b][y < r || y == r && c] = (\
            f[k][l < x || l == x && a][x < y || x == y && b][y < r || y == r && c] + \
                f[k - 1][a][b][c]\
            ) % mod;
        }
        ans = (ans + f[60][1][1][1]) % mod;
    }
    cout << ans;
    return 0;
}
 
}
 
signed main()
{
    return Pozhu :: main();
}

C

输入正整数 $n,m$ ，要求把一个 $n \times m$ 的棋盘染成蓝色和黄色，且每行恰好有一段连续的蓝色的格子，每列恰好有一段连续的黄色的格子。输出总方案数对 $998244353$ 取模的结果。

首先进行一个性质的观察,发现两种颜色的连通块数量必须小于等于 $2$ ，并且不能都为 $1$。

所以直接盗图就可以观察到情况和后边的题解 ：

![](http://xsy.gdgzez.com.cn/JudgeOnline/upload/attachment/image/20220713/20220713024525_57458.png)

![](http://xsy.gdgzez.com.cn/JudgeOnline/upload/attachment/image/20220713/20220713023625_10020.png)

发现题解很详细，为了防止看不懂直接放一下原题链接，这样就有全网的题解了（

CF1503E 2-Coloring

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 400100
const int mod = 998244353;
typedef long long ll;
int n,m,ans;
int fac[N],facinv[N],inv[N];
 
void init(int );
int C(int ,int );
int ksm(int ,int );
void exgcd(int ,int ,int& ,int& );
 
void main()
{
    ios :: sync_with_stdio(false);
    cin >> n >> m;
    init(max(n,m) * 4);
     
    for(int z = 1;z < m;z++){
        int now = 0;
        for(int r1 = n-1;r1 >= 1;r1--)
        {
            (now += (ll) C(r1 + m - z - 1, m - z - 1) * C(n - r1 + m - z - 1, m - z) % mod) %= mod;
            (ans += (ll) C(r1 + z - 1, z) * C(n - r1 + z - 1, z - 1) % mod * now % mod) %= mod;
        }
    }
    for(int p = 1;p <= n;p++){
        int now = 0;
        for(int z1 = 1;z1 < m;z1++)
        {
            (now += (ll) C(n - p + z1 - 2, z1 - 2) * C(n - p + m - z1, m - z1 + 1) % mod) %= mod; 
            (ans += (ll) C(p + z1 - 1, z1) * C(p + m - z1 - 1, m - z1 - 1) % mod * now % mod) %= mod;    
        }
    }
    ans = (ll) ans * 2 % mod;
    cout << ans << '\n';
    return ;
}
 
int C(int n,int m)
{
    if(n < m) return 0;
    return 1ll * fac[n] * facinv[m] % mod * facinv[n - m] % mod;
}
 
void init(int n)
{
    fac[0] = 1;facinv[0] = 1;
    for(int i = 1;i<=n;i++) fac[i] = 1ll * fac[i-1] * i % mod;
    int y;
    exgcd(fac[n],mod,facinv[n],*new int);
    facinv[n] = (facinv[n] % mod + mod) % mod;
    // facinv[n] = ksm(fac[n],mod - 2);
    for(int i = n;i>=2;i--)
    facinv[i-1] = 1ll * facinv[i] * i % mod;
}
 
int ksm(int a,int b)
{
    int ans = 1;
    for(;b;b>>=1,a = 1ll * a * a % mod) if(b & 1) ans = 1ll * ans * a % mod;
    return ans;
}
 
void exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x = 1,y = 0;
        return;
    }
    exgcd(b,a % b,y,x);
    y -= a / b * x;
    return;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

9.13

A

给出两棵 $n$ 个点的有根树 $T_A$ 和 $T_B$ ，这两棵树的根都是 $1$ ，点 $i$ 在 $T_A$ 上的父亲为 $A_i(A_i<i)$ ，在 $T_B$ 上的父亲为 $B_i$ 。

有 $m$ 个询问，对于两个点 $u,v$ ，求一个编号最大的点 $c$ ，使得 $c$ 在 $T_A$ 上是 $u$ 的祖先，在 $T_B$ 上是 $v$ 的祖先。

询问强制在线，第 $i$ 次询问将给出一组 $X_i,Y_i$ ，设第 $i$ 次询问的答案为 $K_i(K_0=0)$ ，那么第 $i$ 次询问中：

做法不是很难理解，懒得打字所以直接盗图了 ：

![](http://xsy.gdgzez.com.cn/JudgeOnline/upload/attachment/image/20220905/20220905074954_92213.png)

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 100010
#define M N * 50
 
int n,m;
int tot;
vector<int>ga[N],gb[N];
int top[N];
int L[N],R[N],dfntot;
int rt[M],ls[M],rs[M],maxx[M];
int ans;
 
void dfs(int );
void build(int ,int );
int query(int ,int ,int ,int );
void update(int ,int ,int& ,int ,int ,int );
 
void main()
{
    scanf("%d%d",&n,&m);
    int x;
    for(int i = 2;i<=n;i++)
    {
        scanf("%d",&x);
        ga[x].emplace_back(i);
    }
    for(int i = 2;i<=n;i++)
    {
        scanf("%d",&x);
        gb[x].emplace_back(i);
    }
    dfs(1),build(1,0);
    int y;
    for(int i = 1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        x = (x + ans) % n + 1;
        y = (y + ans) % n + 1;
        ans = query(1,n,rt[x],L[y]);
        printf("%d\n",ans);
    }
    return;
}
 
int query(int l,int r,int now,int pos)
{
    if(!now) return 0;
    if(l == r) return maxx[now];
    int mid = (l + r) >> 1;
    if(pos <= mid) return max(maxx[now],query(l,mid,ls[now],pos));
    else return max(maxx[now],query(mid+1,r,rs[now],pos));
}
 
void update(int l,int r,int &now,int L,int R,int v)
{
    tot++;
    ls[tot] = ls[now],rs[tot] = rs[now],maxx[tot] = maxx[now],now = tot;
    if(L <= l && r <= R)
    {
        maxx[tot] = max(maxx[tot],v);
        return;
    }
    int mid = (l + r) >> 1;
    if(L <= mid) update(l,mid,ls[now],L,R,v);
    if(mid < R) update(mid+1,r,rs[now],L,R,v);
}
 
void dfs(int x)
{
    L[x] = ++dfntot;
    for(auto i : gb[x]) dfs(i);
    R[x] = dfntot;
}
 
void build(int x,int las)
{
    rt[x] = rt[las];
    update(1,n,rt[x],L[x],R[x],x);
    for(auto i : ga[x]) build(i,x);
    return;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

B

给你 $A,B,C,D$ ，求有多少个正整数 $i$ 满足：

闭区间 $[A+Bi,A+Ci]$ 中没有 $D$ 的整数倍数。
容易证明，答案是有限的。

本题多组数据。

第一行一个数 $t$，表示有 $t$ 组数据。

接下来 $t$ 行，每行 $4$ 个数 $A,B,C,D$ 表示一组数据。

$t$ 行，每行一个数表示这组数据的答案。

$t \le 10^4,1 \le A < D,0 \le B < C < D,2 \le D \le 10^8$

属于是这几天的题里边最简单的一道题了罢……虽然我赛时sb没有切掉

观察数据范围和询问容易猜出这是一道类欧题。

枚举 $i$ 的上界是 ：

所以 $i \le \lfloor \frac{D-2}{C-B} \rfloor$ ，我们设 $m = \lfloor \frac{D-2}{C-B} \rfloor$

容易发现不合法情况数远少于合法情况数（应该是）。

然后考虑用总情况数 $m$ 减去不合法情况数来得到最终答案。

显然对于一个不合法的 $i$ ，在我们现在的限制下满足 ：

而这个差值对所有的 $i$ 来讲要么是 $0$ （合法情况） 要么是 $1$ （非法情况）　

所以我们对合法情况计数也就可以直接计算 ：

最后答案也就是 ：

直接拆开括号之后用类欧计算就行。

代码 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
typedef long long ll;
 
ll a,b,c,d;
 
ll like_gcd(ll a,ll b,ll c,ll n);
 
void main()
{
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    ll m = (d - 1) / (c - b);
    printf("%lld\n",m - like_gcd(c,a,d,m) + like_gcd(b,a-1,d,m));
}
 
ll like_gcd(ll a,ll b,ll c,ll n)
{
    if(!a){return b/c * (n + 1);}
    if(a >= c || b >= c)
    {
        return n * (n + 1) / 2 * (a/c) + (n + 1) * (b/c) + like_gcd(a%c,b%c,c,n);
    }
    ll m = (a * n + b) / c - 1;
    return n * (m + 1) - like_gcd(c,c-b-1,a,m);
}
 
}
 
signed main()
{
    int T;
    for(scanf("%d",&T);T;T--)
    Pozhu :: main();
    return 0;
}

C

现在有 $n$ 个机器人和 $m$ 个出口在一个数轴上，每个机器人和出口都有一个正整数坐标，并且这 $n+m$ 个坐标都互不相同

现在执行若干次操作，每次操作可以是：

  • 将所有机器人的坐标减一
  • 将所有机器人的坐标加一

当一个机器人移到出口的的时候他就会消失，操作将进行直到所有机器人消失

两种操作序列不同，当且仅当存在至少一个机器人在两次操作序列进行完成后从不同的出口消失

给出每个机器人和出口的坐标，求有多少种不同的操作序列，输出方案数对 $10^9+7$ 取模的结果

分析题干，容易发现很显然的性质 ：

  • 一个机器人只会从它左边或右边的洞掉出去，最左边的洞左边的机器人和最右边的洞右边的机器人可以认为没有——因为他们掉进洞的情况只有一种。

所以考虑把每个机器人距离左边的洞和距离右边的洞的距离 $(l,r)$ 看成是这个机器人的两个属性。

如果把从左出看成 $0$ ，从右出看成 $1$ ，那么就是要求对合法的 $01$ 序列计数。

合法的唯一条件就是 ：

如果 $l_i < l_j$ 且 $r_i > r_j$ ，那么 $i$ 为 $1$ 则 $j$ 为 $0$ 。其他情况类似。

所以我们按 $l$ 排序，对于相同的 $l$ 按 $r$ 降序排序。这样条件就变为 $i < j$ 且 $r_i > r_j$ 的时候， $i$ 为 $1$ 则 $j$ 为 $1$。 然后考虑放 $1$ 的方案数，发现就是要选单增的 $r_i$ 的子序列。DP+树状数组优化就好了。注意要离散化。

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 100010
#define lowbit(x) (x & -x)
const int mod = 1e9+7;
 
struct distance{
    int l,r;
    distance(){}
    distance(int _l,int _r) : l(_l),r(_r){}
    friend bool operator < (distance a,distance b)
    {return a.l != b.l ? a.l < b.l : a.r > b.r;}
    friend bool operator == (distance a,distance b)
    {return a.l == b.l && a.r == b.r;}
}d[N];
 
int n,m;
int tot;
int t[N];
int a[N],b[N];
int pre[N],nxt[N];
 
int query(int );
int ksm(int ,int );
void add(int ,int );
 
void main()
{
    scanf("%d%d",&n,&m);
    if(m == 1)
    {
        puts("1");
        return;
    }
    for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
    for(int i = 1;i<=m;i++) scanf("%d",&b[i]);
    int tot =0;
    int L = lower_bound(a+1,a+n+1,b[1]) - a,R = lower_bound(a+1,a+n+1,b[m]) - a - 1;
    for(int i = L;i <= R;i++)
    {
        int x = lower_bound(b + 1,b + m + 1,a[i]) - b;
        d[++tot] = distance(a[i] - b[x-1],b[x] - a[i]);
        nxt[tot] = b[x] - a[i];
    }
    sort(d+1,d+tot+1);
    sort(nxt+1,nxt+tot+1);
    add(0,1);
    for(int i = 1;i<=tot;i++)
    {
        if(d[i] == d[i-1]) continue;
        int x = lower_bound(nxt+1,nxt+tot+1,d[i].r) - nxt;
        int y = query(x-1);
        add(x,y);
    }
    printf("%d",query(n));
    return;
    // printf("%d",ksm(2,tot));
}
 
int query(int x)
{
    int ans = 0;
    for(x++;x;x-=lowbit(x)) ans = (ans + t[x]) % mod;
    return ans;
}
 
void add(int x,int k)
{
    for(x++;x<=n+1;x+=lowbit(x)) t[x] = (t[x] + k) % mod;
}
 
int ksm(int a,int b)
{
    int ans = 1;
    for(;b;b>>=1,a = 1ll * a * a % mod) if(b & 1) ans = 1ll * ans * a % mod;
    return ans;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

by Pozhu
2022.9.14