CYEZ 模拟赛 9

A

$$a\perp b\Rightarrow a-b\perp ab\text{\hspace{1em}(1)}$$

证明：$\gcd (a,b)=\gcd (b,a-b)$，故 $a-b\perp b$，同理 $a-b\perp b$，故 $a-b\perp ab$。

---

题目要求 $a+b\mid ab$，记 $g=\gcd (a,b),a=xg,b=yg$。

$xg+yg\mid xy{g}^2$，得 $x+y\mid xyg$。

由于 $x\perp y$，由 $(1)$ 得 $x+y\perp xy$，得 $x+y\mid g$。

枚举 $i=x+y$，此时，根据 $(1)$ 可得 $x,y$ 的对数即为 $\phi (i)$，而 $(x+y)g\le n$ 且 $x+y\mid g$，可能取值有 $\lfloor \frac{n}{i^2}\rfloor$ 个。

$x+y$ 的上界容易确定，为 $\sqrt{n}$。故答案为 ${\sum }_{i=1}^{\sqrt{n}}\phi (i)\times \lfloor \frac{n}{i^2}\rfloor$。

对于 $\phi$ 函数，考虑线筛时同时处理 $\phi$。

#include<bits/stdc++.h>
#define int long long
using namespace std;const int N = 1e7 + 5;int n, p[N], phi[N], P[N], tot;bool v[N];signed main()
{ios::sync_with_stdio(0); cin.tie(0);cin >> n;int m = sqrt(n), ans = 0;for(int i=2; i<=m; i++){if(!v[i]){phi[i] = i-1;P[++tot] = i;}for(int j=1; i*P[j]<=m and j<=tot; j++){v[i*P[j]] = 1;if(i % P[j] == 0) {phi[i * P[j]] = phi[i] * P[j]; break;}else phi[i * P[j]] = phi[i] * (P[j] - 1);}ans += phi[i] * ((n / i) / i);}cout << ans; 
}

B

简单 LIS 题。

$$f_i=\underset{j<i,a_j<a_i}{\max }{f}_j+1$$

容易用 BIT 优化。

#include<bits/stdc++.h>
#define pii pair <int, int>
#define int long long
using namespace std;const int mod = 123456789;const int N = 1e5 + 5;void chmax(int &A, int &B, int a, int b)
{if(a > A) A = a, B = b;else if(a == A) B += b, B %= mod;
}int n, type, a[N], f[N], g[N];int F[N], G[N];
int lowbit(int x){return x&(-x);}
void modify(int x, int val1, int val2)
{for(;x<=1e5; x+=lowbit(x)) chmax(F[x], G[x], val1, val2);
}
pii query(int x) 
{int res1 = 0, res2 = 0; for(;x>0; x-=lowbit(x)) chmax(res1, res2, F[x], G[x]); return {res1, res2};
}signed main()
{ios::sync_with_stdio(0); cin.tie(0);cin >> n >> type;for(int i=1; i<=n; i++)cin >> a[i];int ansf = 0, ansg = 0;for(int i=1; i<=n; i++){f[i] = 1, g[i] = 1;auto res = query(a[i] - 1);chmax(f[i], g[i], res.first + 1, res.second);modify(a[i], f[i], g[i]);chmax(ansf, ansg, f[i], g[i]);}cout << ansf << "\n";if(type) cout << ansg;
}

C

记 $b_i/w_i$ 为第 $i$ 层的黑色 / 白色节点个数，$s{b}_i/s{w}_i$ 为前 $i$ 层黑色 / 白色节点个数（均指白色节点作为根时）。在本题中，我们认为根节点深度为 $1$。

考虑分别处理 lca 为白色节点和黑色节点的点对：

对于 lca 为白点的点对，两者为祖先 / 后代的关系。距离为 $i$ 的该类型点对数量为 $s{w}_{n-i}\times w_{i+1}$，含义是 $s{w}_{n-i}$ 个节点可能作为祖先，考虑到子树本质相同的性质，对于每个祖先，有 $w_{i+1}$ 个节点与其距离为 $i$。

对于 lca 为黑点的点对，两点一定分别在 lca 的黑白子树中，设白 / 黑子树内两点到 lca 距离分别为 $i,j$，则可能的点对个数为 $w_i\times w_{j+1}$，可能作为祖先的节点个数为 $s{b}_{n-\max (i,j)}$。

#include<bits/stdc++.h>
#define int long long
using namespace std;const int mod = 123456789;
const int N = 5005;int n, w[N], b[N], sw[N], sb[N], ans[N<<1];signed main()
{cin >> n;w[1] = 1, b[2] = 1, w[3] = 1, b[3] = 1;for(int i=4; i<=n; i++)w[i] = (w[i-1] + w[i-2]) % mod,b[i] = (b[i-1] + b[i-2]) % mod;for(int i=1; i<=n; i++)sb[i] = (sb[i-1] + b[i]) % mod,sw[i] = (sw[i-1] + w[i]) % mod;for(int i=1; i<=n; i++)ans[i] = sw[n-i] * w[i+1] % mod;for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)ans[i+j] += (sb[n-max(i,j)] * w[i] % mod) * w[j+1] % mod, ans[i+j] %= mod;for(int i=1; i<=2*n; i++) cout << ans[i] << " ";
}

总结

预估 $100+100+0$，实际 $90+100+0$。场上三题大概都看了眼，发现 T2 比较简单，场上优先写了这题，比较自信，没有写拍。然后开 T1，T1 暴露了我数论接触不多的缺陷，先写了个暴力然后找规律推式子。推完了发现不会筛法求欧拉函数，也不知道一些高深的公式，就推了个奇奇怪怪的基于埃筛的 $O(\sqrt{n}\log \log \sqrt{n})$ 方法。写完代码之后验了几个小数据没什么问题。T3 剩的时间不是很多，想的不是很全面，没有想到根据 lca 去讨论，写了个奇奇怪怪的平方 dp，由于时间不多且分讨巨多没有实现。