2021HDU暑期多校第一场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 112/812 | 6 | 11 | 11 |
B¶
upsolved by JJLeo
题意¶
二维平面上，维护以下两种操作：
- 添加一个点，有对应的权值。
- 询问一个圆内点的权值和。
保证数据随机。(\(1 \le n \le 2 \times 10^5\))
题解¶
KD-Tree 模板，只需更改询问中两个剪枝函数：
- 矩形四个角都在圆内，必然所有点都在圆内，直接返回。
- 矩形内 \(x\) 坐标距离圆心的最小值 \(X\)，和矩形内 \(y\) 坐标距离距离圆心的最小值 \(Y\)，如果 \(X^2+Y^2 > r^2\)，那必然矩形内所有点都不在圆内。
给了 \(10\) 秒，这样就可以卡过去了。
C¶
upsolved by JJLeo
题意¶
给定一个 \(n \times m\) 的方格图，有 \((n-1) \times (m-1)\) 个格子，有 \(n\) 行 \(m\) 列的格子边界，每条边可有可无，一些格子要求其周围的四条边的数量是奇数或偶数，同时要求所有边连成数个简单环，求方案数。(\(2 \le n,m \le 17\))
题解¶
考虑每条边是否存在设为一个 \(01\) 变量，则对于每个有限制的格子可以列出数个异或方程，同时所有边连成数个简单环等价于每个点的度数为偶数，同样可以列出数个异或方程，这个异或方程组解的个数即为答案。
总时间复杂度为 \(O(n^3m^3)\)，可以用 bitset 优化掉一个 \(w\)。
然而，我之前的消元都是假的，但基本都是满秩的情况，所以没出毛病。正确的消元方法是，对于一行，如果该列下面全是 \(0\)，那么就考虑下一列，但并不切换到下一行，这样才能保证所有考虑到的行都有一个关键变量，剩下的变量不管怎么选都可以依靠关键变量使解合法。
无解条件即为没考虑到的行（也就是没有关键变量的行）最后一列有 \(1\)，因为一堆 \(0\) 不能异或出 \(1\)，对于正常的高斯消元这也是成立的。
G¶
upsolved by JJLeo
题意¶
BSGS 裸题，但是我们忘了这个算法的存在。
题解¶
这个算法可以在 \(O(\sqrt p)\) 的时间内求出 \(a^x\equiv b\pmod p\) 的所有解，这玩意其实不太需要模板，稍微写一下原理：
设 \(s=\left\lceil\sqrt p\right\rceil\)，遍历正整数 \(i\in\left[1,s\right],j\in\left[1,s\right]\)，那么 \([0,p-1]\) 的所有数一定会被 \(is-j\) 表示过。
从而原问题转化为 \(a^{is-j}\equiv b\pmod p\)， 即 \(a^{is}\equiv a^jb\pmod p\)，枚举其中一边放 unordered_map 里，再枚举另一边看有没有即可。
I¶
upsolved by JJLeo
题意¶
\(n \times n\) 的二维平面内一些位置有数，同一横坐标只有一个位置有数，多次询问矩形区域内不同纵坐标的个数，可以离线。(\(1 \le n \le 10^5\))
题解¶
因为同一横坐标只有一个位置有数，可以对横坐标范围用莫队，同时对值域分块就可以做到修改 \(O(1)\)，查询 \(O(\sqrt n)\)，总时间复杂度为 \(O((n+q)\sqrt n)\)。
J¶
upsolved by Bazoka13 JJLeo
题意¶
对于一个长度为 \(n\) 且可以旋转的环，有多少本质不同的染色方案：
- 使用红蓝绿染色，绿色最多出现 \(k\) 次。
- 相邻颜色均不同。
(\(3 \le n \le 10^6\))
题解¶
有经典结论：旋转 \(i\) (\(0 \le i < n\)) 次的置换有 \(\gcd(n,i)\) 个环。
考虑使用 Burnside 引理，计算对于每种置换有多少种方案使得置换后不发生变化。考虑对于旋转 \(i\) 次的置换，由于有 \(\gcd(n,i)\) 个环，那么所有相距 \(\gcd(n,i)\) 的位置都必须相同，可以发现这等价于一个长度为 \(\gcd(n,i)\) 的环，只不过将其在大环上重复了 \(\dfrac{n}{\gcd(n,i)}\) 次，如果一个小环出现了 \(x\) 次绿色，则总共出现了 \(\dfrac{nx}{\gcd(n,i)}\) 次绿色，它必须 \(\le k\)。
设 \(f(n,m)\) 为在长度为 \(n\) 的环上放置 \(m\) 个绿色位置的方案数，则最终答案为：
如果 \(m=0\)，显然有 \(f(n,0)=2[n \bmod 2 = 0]\)。
否则，每个绿色位置之间的空隙有 \(2\) 种染色方案，总共有 \(2^m\) 种染色方案，而长度为 \(n\) 的环上选择 \(m\) 个不相邻位置的染色方案可以通过讨论第一个位置是否染色 + 不定方程得出，为 \(\dbinom{n-m}{m}+\dbinom{n-m-1}{m-1}\)。从而有：
最后推下式子，枚举 \(d=\gcd(i,n)\)：
显然 \(\sum \limits _{j=0}^{\left\lfloor\frac{kd}{n}\right\rfloor}f(d,j)\) 至多有 \(O(d)\) 项不为 \(0\)，因此暴力枚举 \(n\) 的约数 \(d\) 后计算，总时间复杂度不超过 \(O\big(\sigma (n)\big)\)，其中 \(\sigma (n)\) 是 \(n\) 的约数和，其规模通过线性筛可知：
| \(n\) | \(\sigma (n)\) 最大值 |
|---|---|
| \(\le 10^6\) | \(4390848\) |
| \(\le 10^7\) | \(45732192\) |
| \(\le 10^8\) | \(487710720\) |
记录¶
总结¶
wls，我的超人！