从十二月份咕到三月份，然后再从第二周咕到第四周的校赛终于开始啦。
虽然是网络预赛，不过题目还是相当有意思的。
C 小张的魔法跳越
\(n(\leq 10^5)\) 个节点的树中，每条边有 unsigned int 的权值 \(w\)，令点对 \((i,j)\) 的最短路径权和为 \(S(i,j)\)，最短路径上所有边权异或和为 \(X(i,j)\)，求 \(\sum_{i<j} S(i,j)\times K(i,j) \pmod {10^9+7}\)。
题解
对边权的每一位单独考虑，则就变成求每一位上异或和为 1 的点对之间的边权和。
类似树上背包的思想，令 \(f(u,0)\) 和 \(f(u,1)\) 表示对节点 \(u\) 当前已经合并的子树中，路径异或和为 0 和 1 的路径的边权之和。更新时，只要用已经处理过的子树，和准备要加入的子树 \(v\) 的 \(f(v,0)\) 和 \(f(v,1)\) 更新答案，再将 \(f(v,0)\) 和 \(f(v,1)\) 合并到 \(f(u,0)\) 和 \(f(u,1)\) 中即可。
总时间复杂度 \(\mathcal{O} (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
| #include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=100000+5;
const int MOD=1000000007;
typedef unsigned int ui;
typedef long long ll;
struct Adj{int v; ui w;};
vector<Adj> a[N];
int ans=0;
int f[N][2],cnt[N][2];
inline bool Judge(ui w,ui p){
return (w&p)>0;
}
void DFS(int u,int pa,ui p){
cnt[u][0]=1;
cnt[u][1]=f[u][0]=f[u][1]=0;
for(int i=0;i<a[u].size();i++){
int v=a[u][i].v;
ui w=a[u][i].w;
if(v==pa)continue;
DFS(v,u,p);
int b=Judge(w,p);
int f1 = (f[v][1^b] + (ll)w*cnt[v][1^b]) %MOD;
int f2 = (f[v][0^b] + (ll)w*cnt[v][0^b]) %MOD;
ans=( ans + (ll)f[u][0] * cnt[v][1^b] %MOD * p )%MOD;
ans=( ans + (ll)f1 * cnt[u][0] %MOD * p )%MOD;
ans=( ans + (ll)f[u][1] * cnt[v][0^b] %MOD * p )%MOD;
ans=( ans + (ll)f2 * cnt[u][1] %MOD * p )%MOD;
cnt[u][0]=(cnt[u][0]+cnt[v][0^b])%MOD;
cnt[u][1]=(cnt[u][1]+cnt[v][1^b])%MOD;
f[u][0]=(f[u][0]+f2)%MOD;
f[u][1]=(f[u][1]+f1)%MOD;
}
}
int main(){
int nCase; scanf("%d",&nCase);
while(nCase--){
int n; scanf("%d",&n);
for(int i=1;i<=n;i++)
a[i].clear();
for(int i=1;i<n;i++){
int u,v; ui w;
scanf("%d%d%ud",&u,&v,&w);
a[u].push_back((Adj){v,w});
a[v].push_back((Adj){u,w});
}
ans=0;
for(int i=0;i<32;i++)
DFS(1,0,((ui)1)<<i);
printf("%d\n",ans);
}
return 0;
}
|
E 禁忌的共鸣
有 \(n(\leq 10^5)\) 个数 \(a_i(\leq 10^5)\)，任意两个数 \((i,j)\) 之间有一条 \((a_i,a_j)\) 的边，求这个图的最大生成树。
题解
显然不能直接搞图出来然后跑 Kruskal。考虑 Kruskal 的贪心原则，从大到小枚举约数，然后将含有这个约数的点全部加入并查集即可。
很诡异的时间复杂度。据说约数个数是 \(\sqrt{n} / \ln{n}\) 级别的，所以我提前处理好每个约数对应的 \(a_i\) 的时间复杂度理论上是 \(\mathcal{O} ( {n^{3/2} / \ln{n}} )\) 级别的。
跟 Potassium（点我跳转）讨论了一下，他是先枚举了约数 \(p\)，然后判断是否存在 \(i\times p=a_i\)。这样的话复杂度是有保证的 \(\sum_{i=1}^n {n/i}= \mathcal{O} (n\log{n})\) 级别。
果然还是不能什么都用 vector
代码
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
| #include<iostream>
#include<ctime>
#include<vector>
using namespace std;
typedef long long ll;
const int N=100000+5;
vector<int> fac[N];
vector<int> edg[N];
int n;
void FindFac(){
for(int i=1;i<N;i++)
for(int j=i;j<N;j+=i)
fac[j].push_back(i);
}
int pa[N];
int FindPa(int x){
return pa[x]==x?x:pa[x]=FindPa(pa[x]);
}
ll Kruskal(){
ll ans=0; int cnt=0;
for(int i=N-1;i>0;i--){
if(edg[i].size()>1){
for(int j=1;j<edg[i].size();j++){
int u=edg[i][0],v=edg[i][j];
int paU=FindPa(u),paV=FindPa(v);
if(paU!=paV){
ans+=i; cnt++;
pa[paU]=paV;
if(cnt==n-1)return ans;
}
}
}
}
}
void Init(){
for(int i=1;i<=n;i++)
pa[i]=i;
for(int i=1;i<N;i++)
edg[i].clear();
}
int main(){
FindFac();
int nCase; scanf("%d",&nCase);
while(nCase--){
scanf("%d",&n);
Init();
for(int i=1,a;i<=n;i++){
scanf("%d",&a);
for(int j=0;j<fac[a].size();j++)
edg[fac[a][j]].push_back(i);
}
printf("%lld\n",Kruskal());
}
return 0;
}
|
F zzh 与同余方程
令 \(m\in S(i)\) 为 \(i\) 相关的同余方程的解：
\[(i+1)^{i+1}\equiv (i+1)^{i}\pmod{m}\]
多次询问，求 \(\sum _{i=1}^n |S(i)| \pmod {998244353}\)，其中 \(n\leq 10^7\)。
题解
题目本质是要求 \(m \mid i(i+1)^i\) 的所有 m，也就是 \(i(i+1)^i\) 的因数个数。注意到当 \((i,i+1)=1\)，因此只要分别处理出每个数 \(i\) 有多少个不同的质因数和每个质因数的数目 \(k_i\) 即可。
由约数个数公式可知，对 \(p=\prod p_i^{k_i}\)，有约数个数 \(D(p)=\prod (k_i+1)\)，\(D(p^q)=\prod (k_i*q+1)\)。因此只要筛出所有素数，然后用素数筛掉它的倍数计算每个 \(p\) 的 \(k_i\) 即可。
时间复杂度：一个数的质因数分解中最多有 \(\log_2 {n}\) 个数，每个数 \(p\) 都会被每个质因数一直筛到 1，因此时间复杂度是 \(\mathcal{O} (n\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
| #include<cstdio>
#include<iostream>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N=10000000+5,MOD=998244353;
int ans[N];
bool notPri[N];
int pri[N];
void Euler(){
for(int i=2;i<N;i++){
if(!notPri[i])
pri[++pri[0]]=i;
for(int j=1;j<=pri[0]&&i*pri[j]<N;j++){
notPri[i*pri[j]]=1;
if(i%pri[j]==0)break;
}
}
}
void FindFac(){
for(int i=1;i<N;i++)ans[i]=1;
for(int i=1;i<=pri[0];i++){
for(int j=pri[i];j<N;j+=pri[i]){
int cnt=0,tmp=j;
while(tmp%pri[i]==0){
tmp/=pri[i];
cnt++;
}
ans[j-1]=1LL*ans[j-1]*(1LL*cnt*(j-1)%MOD+1)%MOD;
ans[j]=1LL*ans[j]*(cnt+1)%MOD;
}
}
}
void Process(){
for(int i=1;i<N;i++){
ans[i]=(ans[i]+ans[i-1])%MOD;
}
}
int main(){
Euler();
FindFac();
Process();
int nCase; scanf("%d",&nCase);
while(nCase--){
int x; scanf("%d",&x);
printf("%d\n",ans[x]);
}
return 0;
}
|
G 小 z 刷题
给定 \(n(\leq 10^5)\) 个数对 \((a_i,p_i)\) 表示一个连续的序列，一个数对表示数列的一部分，该部分由 \(p_i\) 个 \(a_i\) 构成。令 \(S(x)\) 表示该序列中长度为 \(x\) 的上升子序列个数，求 \(\sum x^k \times S(x) \pmod {10^9+7}\)，其中 \(k\leq 20\)。
题解
很优美的一道题目。
假设已经知道前 \(n\) 个数中满足 \(a_i<a_{n+1}\) 的 \(\sum x^k \times S(x)\)，考虑加入下一个数 \(a_{n+1}\)。显然在原有答案末尾加入 \(p_{n+1}\) 个 \(a_{n+1}\) 后可以对答案做出贡献。下式进行二项式展开：
\[
\begin{aligned}
\sum_x p_{n+1} \times (x+1)^k \times S(x) &= \sum_x p_{n+1} \times \sum_{i=1}^k \binom{k}{i}x^i \times S(x) \\
&= \sum_{i=1}^k \binom{k}{i} p_{n+1} \sum_x x^i \times S(x)
\end{aligned}
\]
即对新加入的结果，可以由满足 \(a_i<a_{n+1}\) 部分的 \(\sum x^t \times S(x), t=0,1,2,\dots,k\) 结果计算出来。因此离散化之后可以用树状数组维护 \(t\) 次方下的答案并更新。
总时间复杂度 \(\mathcal{O} (n\log {n}+nk^2)\)。
代码
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<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100000+5,MOD=1000000007,K=20+2;
struct BITree{
int t[N];
BITree(){
Clear();
}
void Clear(){
memset(t,0,sizeof(t));
}
int Lowbit(int x){
return x&(-x);
}
void Add(int x,int v){
for(;x<N;x+=Lowbit(x))
t[x]=(t[x]+v)%MOD;
}
int Query(int x){
int ret=0;
for(;x;x-=Lowbit(x))
ret=(ret+t[x])%MOD;
return ret;
}
};
BITree b[K];
int v[N],p[N],pos[N];
int c[K][K];
int n,k;
void InitComb(){
for(int i=0;i<K;i++){
c[0][i]=1;
for(int j=1;j<=i;j++)
c[j][i]=(c[j][i-1]+c[j-1][i-1])%MOD;
}
}
int main(){
InitComb();
int nCase; scanf("%d",&nCase);
while(nCase--){
int n,k; scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d%d",&v[i],&p[i]);
pos[i]=v[i];
}
sort(pos+1,pos+n+1);
for(int i=0;i<=k;i++)
b[i].Clear();
int ans=0;
for(int i=1;i<=n;i++){
int idx=lower_bound(pos+1,pos+n+1,v[i])-pos;
int tmpSum[K];
for(int j=0;j<=k;j++)
tmpSum[j]=b[j].Query(idx-1);
for(int j=0;j<=k;j++){
int tmpAns=1;
for(int l=0;l<=j;l++)
tmpAns=(tmpAns+1LL*tmpSum[l]*c[l][j])%MOD;
tmpAns=1LL*tmpAns*p[i]%MOD;
b[j].Add(idx,tmpAns);
if(j==k)ans=(ans+tmpAns)%MOD;
}
}
printf("%d\n",ans);
}
return 0;
}
|
I Ange 的 DNA 自动机
定义矩阵：
\[
\begin{aligned}
A &= \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\\
T &= \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\\
C &= \begin{bmatrix} -1 & 0 \\ 0 & 1 \end{bmatrix}\\
G &= \begin{bmatrix} -1 & 0 \\ 0 & -1 \end{bmatrix}
\end{aligned}
\]
给定长度为 \(n(\leq 10^6)\) 的字符串 \(S=\{s_1,s_2,\dots,s_n\}\)。定义一次操作 \(S \rightarrow T：\)
\[t_i = s_i \times s_{(i \bmod n) +1}\]
求经过 \(k(\leq 10^9)\) 次这样操作后的字符串 \(T\)。
题解
经过很显然的手推可以发现，令 \(A,T,G,C\) 分别代表 \(0,1,2,3\)，并定义乘法为异或操作的情况下，计算方法和原式等价。
假设 \(f(k,i)\) 表示操作 \(k\) 次后的串的第 \(i\) 个数，则再一次经过很显然的手推可以发现有如下关系：
\[f(k,i)=f(k-{2^t},i)\otimes f(k-{2^t},i+2^t)\]
其中 \(\otimes\) 表示异或操作，\(t\) 是满足 \(k-2^t > 0\) 的最大 \(t\)（也就是 \(k\) 在二进制下的最高位）。这个递归是 \(\mathcal{O} (\log k)\) 级别的，因此总时间复杂度 \(\mathcal{O} (n\log k)\)。
中间传 vector 太多导致第一次 T 掉了。还是要看场合使用啊。
代码
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
| #include<iostream>
#include<cstdio>
#include<vector>
#include<ctime>
using namespace std;
const int N=1000000+5,K=32;
char ch[K][N];
int n;
int Highbit(int x){
for(int i=30;i>=0;i--)
if(x&(1<<i))return 1<<i;
return 0;
}
char* NextXOR(int t,int dep){
if(t==0)return ch[0];
int valHB=Highbit(t);
char* pre=NextXOR(t-valHB,dep+1);
char* ret=ch[dep];
for(int i=0;i<n;i++)
ret[i]=(pre[i]^pre[(i+valHB)%n]);
return ret;
}
int main(){
int nCase; scanf("%d",&nCase);
while(nCase--){
int k; scanf("%d%d\n",&n,&k);
char* arr=ch[0];
for(int i=0;i<n;i++){
char c; scanf("%c",&c);
if(c=='A'){
arr[i]=0;
}else if(c=='T'){
arr[i]=1;
}else if(c=='G'){
arr[i]=2;
}else if(c=='C'){
arr[i]=3;
}
}
char* ret=NextXOR(k,1);
for(int i=0;i<n;i++){
if(ret[i]==0)
printf("A");
else if(ret[i]==1)
printf("T");
else if(ret[i]==2)
printf("G");
else if(ret[i]==3)
printf("C");
}
printf("\n");
}
return 0;
}
|
总结
是一套很有意思的题目和一位很菜的参赛者。
有两处错误都是因为中途爆了 long long 而 WA 掉了，并且一开始都没有找出原因来。深刻反省深刻反省。只要有 long long 和相乘的地方，都需要思考到底会不会爆 long long。
有一个比较隐式的爆法是，\(x\) 每次都有可能变为 \(\left \lfloor {x\over p} \right \rfloor\)，其中 \(1\leq p \leq 20\)。\(p=1\) 的情况下相当于 \(x\) 每次都增加一倍，这个时候就会爆掉了。
明天的线下赛也要加油啊。