洛谷8月月赛小结

ddd @ 2017-08-06 01:22:44

by ddd @ 2017-08-06 01:23:00

Problem A(By krydom)

算法1

注意到一个质数只有 1 和本身 2 个因子，所以不能分解为 2 个 \ge 2 的数的乘积，直接输出 0 即可，可以通过 10% 的测试点。

算法2

我们用 dfs(x, y) 来解决当前已经分解了 x 个数，要继续分解 y 的方案数.我们设 p[i] 为第 i 次分解出来的数，只要找到一个大于、小于 p[i-1] 的数继续分解即可。可以通过 20% 的测试点。

算法3

我们令 f[i][j] 表示：分解 i ，且分解出来的数中有一个 j ，其他数 <j 的方案数。若 j \nmid i，则 f[i][j] = 0。于是我们就很容易能写出转移方程：f[i][j] = \sum f[\frac{i}{j}][k], (k < j)。我们可以计算得到 \le 10^7 的数中最多只有 448 个因数。设因数的数量为 m，可以用记忆化 + map 把时间复杂度变为 O(m ^ 3 log n)。可以 50% 的测试点。

小优化 :

用 a[i] 表示 n 从小到大的第 i 个因数。用 b[i] 表示 i 这个数是 n 的第几个因数，这可以用二分/哈希 O(\log{n}) 或 O(1) 得到。用 f[i][j] 表示：分解 a[i]，且分解出来的数中有一个 a[j]，其他数 <a[j] 的方案数。若 a[j] \nmid a[i] 则 f[i][j] = 0，否则f[i][j] = \sum f[b[\frac{a[i]}{a[j]}]][k], (k < j)。枚举 k，时间复杂度O(m^3logm) 或 O(m^3)，可以通过 50% 的测试点。

算法4

我们尝试着优化50%的数据的dp：

再观察一下这个式子f[i][j] = \sum f[b[\frac{a[i]}{a[j]}]][k], (k < j)，可以发现 f[i][j] 就是 f[b[a[i] / a[j]] 这个数组的一个前缀和。记录 sum[i][j] = \sum_{k=1} ^ j a[i][k]，

转移的时候直接找到位置转移即可。时间复杂度 O(m ^ 2) 或者 O(m ^ 2 log m)。

对于任何 \le 10 ^ {12} 的数， m 最大是 6720，所以可能会导致一些选手因常数问题挂掉最后一个点，没错我就是故意的。但是可以发现，m > 5000 的数其实不多，只有几百个。所以我们可以先预处理出所有 m > 5000 的数的答案打一下表，就把 m 变成了 <5000 的数。可以通过 100% 的测试点。

标程打表的原因是因为出题人太菜太懒而且自带大常数。

而且因为答案非常小，是不需要取模的。

by ddd @ 2017-08-06 01:23:18

Problem B(By ddd)

算法1

枚举每个点选或不选，暴力判断是否可行，并统计答案。复杂度O(2^nn)，可以通过 10% 的测试点。

算法2

注意到 9.99\times 10^2 \leq n \leq 10^3 意味着 n=999 或 n=1000，通过优化的爆搜或者其它手段得出答案，打表即可，可以通过 20% 的测试点。

算法3

容易发现，删去一条边后的圈数 = 不删边的圈数 - 含有某条定边的圈数。设 a[n] 为 n 个点的无向完全图不删边的圈数，b[n] 为 n 个点的完全无向图含有某条定边的圈数。可以发现

递推即可。时间复杂度 O(n)，可以通过 60% 的测试点。

算法4

和上一个算法一样，仍然考虑两种情况。

现在考虑不删边的情况：构成一个圈，至少需要 3 个节点，至多有 n 个节点。任选出 k 个节点，这 k 个节点可以组成的圈数即为这 k 个点的圆排列除以 2，除以 2 是因为正反排列在圆排列中算作两个，而在图中视为一种，所以圈数即为 \sum_{k=3}^{n}\frac{\binom{n}{k}\times k!}{2k}。

再考虑含有某条定边的圈数：将这条边的两个点固定，从剩下的 n - 2 个节点中至少选 1 个点，最多选 n - 2 个点。任选出 k 个点，这 k 个点的任意一种排列加上固定的那两个点都构成一个圈，所以圈数即为 \sum_{k=1}^{n-2}\binom{n-2}{k}k!。

所以本题的答案即为两数做差，直接计算即可。复杂度 O(n)，可以通过 60% 的测试点。

算法5

注意到数据范围很特殊，所以按照算法3暴力得出 n=9.99\times 10^8 时的a[n],b[n]，从这个基础上递推即可，可以通过 100% 的测试点。

算法6

注意到对于 n>998244353，当 i>n-998244353 时，A_{n}^{i} 在模意义下为 0。所以当 n>998244353 时，算法4中的式子只需要算到较小的范围。时间复杂度 O(n-998244353)，可以通过 100% 的测试点。

注意：

尽管对于 k=998244353 时，A_{n}^{k}=0，但是由于分母也为 998244353，所以会消去，故这一项在模意义下不为 0，所以需要特殊处理一下这一项。打表得出 \frac{10^9!}{998244353} \bmod 998244353，再处理即可。

by ddd @ 2017-08-06 01:23:30

Problem C(By ddd)

算法1

每次操作都在上次操作的基础上拷贝一份，然后再进行。查询的时候在历史版本暴力查询。时间复杂度 O(qn)，可以通过 30% 的测试点。

算法2

对于每个修改操作，记录下这次操作的区间、值。对于查询操作，在历史的修改操作中找到对该点有影响的修改，并作用到该点，同时统计答案，时间复杂度O(q^2)。但是由于每次查询都是在过去的修改中查找，所以常数很小。可以通过 70% 的测试点。

算法3

将询问离线，在数轴上将修改操作记录下来，形如 (pos,ADD/DEL,time,value)。再把询问从数轴上记录下来，形如 (pos, time, value)。在数轴上从 0 到 n 扫描，维护该位置的值随时间的变化的序列。

扫描到 i 时，先将该位置上ADD操作作用到序列上，即将序列的 [time,q] 加上 value。再消除上一个位置的DEL操作的影响，方法类似。再给整体加上 a[i]-a[i-1]，这个可以整体打标记。对于该位置的查询，只需要查询在 [0,time-1] 内有多少个 \geq value 的值。所以现在需要一个可以做到区间加、区间查询rank的数据结构。这个可以使用分块来解决：

将序列分成若干块，每块 k 个元素，一共 O(\frac{n}{k}) 块，每块维护一个有序的序列。对于加操作，整块内直接打标记，零散部分暴力修改后重构，重构时因为是两部分有序序列合并到一起，所以可以线性时间复杂度内归并起来，这个操作的复杂度是 O(\frac{n}{k}+k)。对于查询操作，整块内直接在有序序列内二分即可，零散部分暴力处理，这个操作的复杂度是 O(\frac{n}{k}\log{\frac{n}{k}} + k)。经计算可得取 k=\sqrt{n\log{n}} 时总复杂度最小（但是因为修改操作比查询要多，所以要适当调整系数），总复杂度 O((n+q)\sqrt{q\log{{q}}})，可以通过 100% 的测试点。

算法4（by kczno1）

把时间分成 \sqrt{q} 块，对每一块，按修改操作把序列分成 \sqrt{n} 块。先把块内的所有修改作用到序列上，对于每个询问在序列上二分。总复杂度 O(q\sqrt{n}\log{\sqrt{n}})，但是由于常数很小，比上一个算法还要快，可以通过 100% 的测试点。

by noip @ 2017-08-06 01:43:02

分块大师

话说T3

算法5（by nzhtl1477）

通过黑魔法总复杂度O( ( n + q ) sqrt( n ) )

比所有算法都快，可以通过 100% 的测试点。

by ddd @ 2017-08-06 01:49:41

@noip

by BlueArc @ 2017-08-06 06:37:40

辛苦了

by icy @ 2017-08-06 06:42:10

凌晨一点更新题解。。

辛苦了

mark一下赶紧学习一下→_→

by BlueArc @ 2017-08-06 06:59:02

这么多字看着就厉害

by Hail_SHEILD @ 2017-08-06 07:29:52

ddd辛苦了~

不过有std吗？

by 神姬2016 @ 2017-08-06 07:41:51

所以神秘奖励是什么、、、