Post 93

背影却,重叠回那少年。

[SCOI2016]萌萌哒

题目描述

一个长度为 $n$ 的大数,用 $S_1S_2S_3 \cdots S_n$表示,其中 $S_i$ 表示数的第 $i$ 位, $S_1$ 是数的最高位。告诉你一些限制条件,每个条件表示为四个数,$l_1,r_1,l_2,r_2$,即两个长度相同的区间,表示子串$S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1}$与$S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2}$完全相同。
比如 $n=6$ 时,某限制条件 $l_1=1,r_1=3,l_2=4,r_2=6$ ,那么 $123123$,$351351$ 均满足条件,但是 $12012$,$131141$ 不满足条件,前者数的长度不为 $6$ ,后者第二位与第五位不同。问满足以上所有条件的数有多少个。

输入输出格式

输入格式:
第一行两个数n和m,分别表示大数的长度,以及限制条件的个数。
接下来m行,对于第i行,有4个数 li1,ri1,li2,ri2,分别表示该限制条件对应的两个区间。
$1\le n\le 10^5$,$1\le m\le 10^5$ ,$ 1\le li1,ri1,li2,ri2 \le n $ ;并且保证 $ ri1-li1=ri2-li2 $ 。
输出格式:
一个数,表示满足所有条件且长度为n的大数的个数,答案可能很大,因此输出答案模 $ 10^9+7 $ 的结果即可。

输入输出样例

输入样例#1:
4 2
1 2 3 4
3 3 3 3

输出样例#1:
90

题解

身负重病依然想写题.jpg

结果根本想不出来还在硬想。

一个暴力的做法是直接用一个维护集合大小的并查集来暴力合并,合并完了把每个集合的大小记为$k_i$,答案就是$\sum 10^{k_i}$。时间复杂度$O(n^2)$

然后WA了,遂整起了WSL。


[SDOI2015]约数个数和

题目描述

数据范围:$1\leqslant N,M,T\leqslant 5\times 10^4$

首先给出一个公式:

因此所求为

改变求和顺序,先枚举因数 $x$ 和 $y$

将 $x,y$ 换成 $i,j$ 吧 QAQ

开始莫比乌斯反演!设

则有

我们把 $x$ 提出就可以消除 $\gcd$ 的影响

再根据 $f(x)$ 的定义,得到答案为 $f(1)$
又因为

接下来再考虑如何求 $g(x)$,我们可以先计算 $s(x)=\sum\limits_{i=1}^{x} \left\lfloor\frac{x}{i}\right\rfloor$,就可以 $\Theta(1)$ 计算 $g(x)$。
时间复杂度:$\Theta(T\sqrt{n})$

Extended
如何证明 Solution 中的公式?

我们考虑把每个因子一一映射。
如果 $ij$ 的因子 $k$ 中有一个因子 $p^c$,$i$ 中有因子 $p^a$,$j$ 中有因子 $p^b$。我们规定:

如果 $c\leqslant a$,那么在 $i$ 中选择。
如果 $ca$,那么我们把 $c$ 减去 $a$,在 $j$ 中选择 $p^{c-a}$(在 $j$ 中选择 $p^e$ 表示的是 $p^{a+e}$)

对于 $ij$ 的因子 $k$ 的其他因子同理。于是对于任何一个 $k$ 有一个唯一的映射,且每一个选择对应着唯一的 $k$。
通过如上过程,我们发现:对于 $ij$ 的因子 $k=\prod {p_i}^{c_i}$,我们不可能同时在 $i$ 和 $j$ 中选择 $p_i$(优先在 $i$ 中选择,如果不够就只在 $j$ 中选择不够的指数),故 $x$ 和 $y$ 必须互质。
等式得证。

哈,真有趣,这是我学的Mobius inversion?

[国家集训队]Crash的数字表格

求解(对 $20101009$ 取模)

数据范围:$n,m\leqslant 10^7$

Solution

比天守阁的地板要简单。

易知原式等价于

枚举最大公因数 $d$,显然两个数除以 $d$ 得到的数互质

非常经典的 $\gcd$ 式子的化法

后半段式子中,出现了互质数对之积的和,为了让式子更简洁就把它拿出来单独计算。于是我们记

接下来对 $\operatorname{sum}(n,m)$ 进行化简。首先枚举约数,并将 $[\gcd(i,j)=1]$ 表示为 $\varepsilon(\gcd(i,j))$

设 $i=i’\cdot d$,$j=j’\cdot d$(其中 $i’,j’$ 指上式中的 $i,j$ ),显然式子可以变为

观察上式,前半段可以预处理前缀和;后半段又是一个范围内数对之和,记

可以 $\Theta(1)$ 求解
至此

我们可以 $\lfloor\frac{n}{\lfloor\frac{n}{d}\rfloor}\rfloor$ 数论分块求解 $\operatorname{sum}(n,m)$ 函数。时间复杂度是$O(\sqrt{n})$
在求出 $\operatorname{sum}(n,m)$ 后,回到定义 $\operatorname{sum}$ 的地方,可得原式为

可见这又是一个可以数论分块求解的式子!
本题除了推式子比较复杂、代码细节较多之外,是一道很好的莫比乌斯反演练习题!(上述过程中,默认 $n\leqslant m$)
关于时间复杂度,这可真是难倒了数学不好的我

我们来分析一下。

如果最后的答案不使用根号优化,复杂度是

$O(\sum\limits_{i=1}^{n}\sqrt{\frac{n}{i}})$

然而这并不能算,但是我们把$\frac{n}{i}$的下取整去掉,求和换积分算子,那么放缩后求出来的复杂度

是$O(n)$(尽管听上去不科学,$\sum_{i=1}^{n} \frac{n}{i} = lnn + \gamma$)

验证:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
int n;
int main()
{
scanf("%d",&n);
int ct = 0;
for(int i = 1 ; i <= n ; i = n / (n / i) + 1)
ct += std::sqrt(i);
ct += std::sqrt(n);
printf("%d\n",ct);
}

然后我求了一下1000000000,发现复杂度是14918223???

貌似不像线性。这个复杂度明显有误.

明天再搞。

来补坑。

直接考虑最终优化的复杂度怎么算。

首先如果我们想用积分,准确来说是定积分,我们应该积一个连续区间。

显然最后取值是$1到2\sqrt{n}$(最大)

那么复杂度就是$\int_{1}^{2\sqrt{n}}\sqrt{x} ~dx$

这个积分大家都会求,忽略常数是$O(n^{\frac{3}{4}})$