伊埃斯的小站
日记

日记

Tue Nov 26 2024
9 分钟
life 日记
1385 字

上午#

考试啊，也是根本做不出来。先看了T1，是道简单的树形dp（不会做法假了吧）。T2就直接给我创飞，只能打个 3030 分暴力（正解似乎是dp？）。然后，也是头昏脑涨，便睡趴了十五分钟，然后再来想T2。想的实在是没有头绪，就来写日记，给脑子初始化一下，再去想了。今天这个考试，标题是C组，然而题目标题是B组。
表里不一的模拟赛链接 看不太懂的题解

T1：给你一个森林，然后让你求每颗树的直径和。
是个学过树形dp的人都会打吧。10min10min 就打出来。但是我去上厕所的时候，看见 yzp 调了半个小时多，不会又 RE 了吧

T2：定义一个子区间的价值是整个子区间里所有的数的 gcdgcd 乘上子区间里所有数的和。
先想到想到了线段树维护区间和和区间 gcdgcd ，然后 O(n2)O(n^2) 暴力，总时间复杂度 O(n2logn)O(n^2logn) 。然后过了 10min10min 又想到了 O(n2)O(n^2) 的做法，也算是一大进步，优化掉了一个 lognlogn 。

T3：求众数出现次数大于区间长度的一半的子区间个数。
打一个 O(n3)O(n^3) 暴力，能拿 1010 分（蚊子肉也是肉嘛）

T4：暴力都不想打（每次都这样）
算了，还是试试T4的暴力吧。

总结：还是 大菜特菜 ，还得练（还得练到什么时候去啊）

然后就考完了，反方向的rank4，退役得了。

然后，熊老师说发题解，然而并没有（皇帝的新题解），于是我就去做dp了，我的dp实在太菜了。

我什么时候能再场切一道蓝题呢？

下午#

也是改题。那个私人题解，给的是部分分题解也不说一声，害得我浪费了半个小时，在讲T2前极限改出来。

T1：场切不说。

T2：source
先说那个题解给的私人部分分做法：设值域的上界是 VV ，gcd(l,r)gcd(l,r) 为 ll 到 rr 的区间 gcdgcd ，则 gcd(1,r),gcd(2,r),gcd(3,r),...gcd(r,r)gcd(1,r),gcd(2,r),gcd(3,r),...gcd(r,r) 至多有 logVlogV 个取值。 枚举每一个右端点 rr ，设在 rr 的 logVlogV 个取值里，有一个取值为 xx ，则对于每一个 xx ，二分查找最靠左的左端点 ll 使得 gcd(l,r)=xgcd(l,r) = x。时间复杂度 O(n×logn×log2n)O(n \times logn \times log^2n) 。
再说正解：在那 logVlogV 个 gcdgcd 的取值里，我们发现对于每个取值，加一个之后，它就会变成它和 hih_i 的 gcdgcd 。这样我们就可以 logVlogV 更新每一个 gcdgcd 。时间复杂度 O(nlogV)O(nlogV)

T3&T4：没改，晚上再说

晚上#

先玩了一会原神（当然是下课玩的，上课没有），然后看到方大三抽出林尼，欸这您受得了吗。

T4：source solution
这个题目解法用文字描述实在是太繁琐了（其实是我不想写，也不会写），于是把代码打在这里好了。

CPP
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
#include<bits/extc++.h>
#define int long long
using namespace std;
const int maxn = 65;
const int mod = 1e9 + 7;
int n,m,k;
int head[maxn],idx;
int f[maxn][10],dep[maxn];
int fa[maxn],l[20];
int c[20],d[20];
struct edge
{
    int v,nxt;
    edge(int v = 0,int nxt = 0):v(v),nxt(nxt){};
}e[maxn << 1];
void adde(int u,int v)
{
    e[++idx] = edge(v,head[u]);
    head[u] = idx;
}
int binpow(int x,int y)//快速幂
{
    int ret = 1;
    while (y)
    {
        if (y & 1)
            ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}
void dfs(int u,int fa)//lca预处理
{
    f[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for (int i = 1; i < 10; i++)
        f[u][i] = f[f[u][i - 1]][i - 1];
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (v == fa)
            continue;
        dfs(v,u);
    }
}
int lca(int u,int v)//最近公共祖先
{
    if (dep[u] < dep[v])
        swap(u,v);
    for (int i = 9; i >= 0; i--)
        if (dep[u] - (1 << i) >= dep[v])
            u = f[u][i];
    if (u == v)
        return u;
    for (int i = 9; i >= 0; i--)
        if (f[u][i] != f[v][i])
            u = f[u][i],v = f[v][i];
    return f[u][0];
}
void init()//并查集初始化
{
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}
int find(int x)//并查集查找
{
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    for (int i = 1; i < n; i ++)
    {
        int u,v;
        scanf("%lld%lld",&u,&v);
        adde(u,v);
        adde(v,u);
    }
    dfs(1,0);
    for (int i = 1; i <= m; i++)
    {
        scanf("%lld%lld",c + i,d + i);
        l[i] = lca(c[i],d[i]);//预处理lca
    }
    int ans = binpow(k,n - 1),g,sum;
    int tmp1,tmp2,st,en;
    for (int i = 1; i < (1 << m); i++)
    {
        g = 1,sum = 0;
        init();
        for (int j = 0; j < m; j++)
        {
            if (i & (1 << j))
            {
                g = -g;//容斥的正负性
                st = c[j + 1];//从一个点到lca
                while (st != l[j + 1])
                {
                    if (f[st][0] == l[j + 1])
                        break;
                    tmp1 = find(st),tmp2 = find(f[st][0]);
                    if (tmp1 != tmp2)
                        fa[tmp1] = tmp2;//合并连通块
                    st = f[st][0];//往上跳
                }
                en = d[j + 1];//从另一个点到lca
                while (en != l[j + 1])
                {
                    if (f[en][0] == l[j + 1])
                        break;
                    tmp1 = find(en),tmp2 = find(f[en][0]);
                    if (tmp1 != tmp2)
                        fa[tmp1] = tmp2;//合并连通块
                    en = f[en][0];//往上跳
                }
                if (st != l[j + 1] && en != l[j + 1])
                {
                    tmp1 = find(st);
                    tmp2 = find(en);
                    if (tmp1 != tmp2)
                        fa[tmp1] = tmp2;
                }//如果都不是lca就把两个点合并
            }
        }
        for (int j = 2; j <= n; j++)
            if (fa[j] == j)
                sum ++;//计数连通快
        ans = (ans + g * binpow(k,sum) % mod + mod) % mod;//记录答案
    }
    ans = (ans + mod) % mod;
    cout << ans;
    return 0;
}

打完了它还 WA 了一次，死因：没开 long long （虽然这也不是第一次）。

然后就只剩 2020 分钟了，切点水题吧。