zcmimi's blog
avatar
zc
2020-06-11 16:49:00
查看原题

点击跳转

f_i表示所有数\gcdi还要加入的数的期望数量

ans=1+\frac{\sum_{i=1}^mf_i}m

可以知道f_1=0

f_i=1+\frac{\sum_{j=1}^m f_{\gcd(i,j)}}m(i>1)

继续推式子:

\begin{aligned} f_i &=1+\frac{\sum_{j=1}^m f_{\gcd(i,j)}}m\\ &=1+\frac{\sum_{d|i} f_d\sum_{j=1}^m [\gcd(i,j)=d]}m \end{aligned}

把分子拿出来

\begin{aligned} &\quad\sum_{d|i} f_d\sum_{j=1}^m [\gcd(i,j)=d]\\ &=\sum_{d|i} f_d\sum_{j=1}^{m/d} [\gcd(\frac id,j)=1]\\ &=\sum_{d|i} f_d\sum_{j=1}^{m/d} \sum_{x|\frac id,x|j}\mu(x)\\ &=\sum_{d|i} f_d \sum_{x|\frac id}\sum_{j=1}^{m/dx}\mu(x)\\ &=\sum_{d|i} f_d \sum_{x|\frac id}\mu(x)\left \lfloor \frac m{dx}\right\rfloor\\ \end{aligned}\\

T=dx

=\sum_{T|i}\sum_{d|T} f_d \mu(\frac Td)\left \lfloor \frac mT\right\rfloor

带入原来的式子

f_i=1+\frac{\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)}m

F_T=\sum_{d|T} f_d \mu(\frac Td)

d\not = i时可以每算出一个f_i就更新所有F_x(i|x)

d=i时没法直接更新,这时T=d=i,\mu(\frac Td)=\mu(1)=1

f_i=1+\frac{\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m+\frac{f_i\left\lfloor \frac mi \right\rfloor}m \\ f_i-\frac{f_i\left\lfloor \frac mi \right\rfloor}m=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m \\ f_i\frac{m-\left\lfloor\frac mi \right\rfloor}m=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m \\ f_i=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}{m-\left\lfloor\frac mi \right\rfloor}

这样就可以先算f_i,再算F_i

[d\not=i]这个条件只在T=i的时候才有限制

枚举到T=i,计算f_i时,F_x(x<i)都已经计算好了

F_i还少了f[i] \times \mu(1)

这正好是要剪掉的部分

avatar
zc
2020-06-09 16:10:00
查看原题

点击跳转

a_i=\sum\limits_{j=1}^N[A_j=i],n=10^6

\sum_{i=1}^n\sum_{j=i+1}^n \operatorname{lcm}(A_i,A_j)\\ =\sum_{i=1}^n\sum_{j=i+1}^n a_ia_j\frac{ij}{\gcd(i,j)}\\ =\sum_{d=1}^n\frac 1d\sum_{i=1}^n\sum_{j=i+1}^n a_ia_j ij [\gcd(i,j)=d]\\ =\sum_{d=1}^n\frac 1d\sum_{i=1}^{n/d}\sum_{j=i+1}^{n/d} a_{id}a_{jd} idjd [\gcd(i,j)=1]\\ =\sum_{d=1}^n d \sum_{i=1}^{n/d}\sum_{j=i+1}^{n/d} a_{id}a_{jd} ij [\gcd(i,j)=1]\\ =\sum_{d=1}^n d \sum_{i=1}^{n/d}\sum_{j=i+1}^{n/d} a_{id}a_{jd} ij \sum_{x|i,x|j}\mu(x)\\ =\sum_{d=1}^n d \sum_{x=1}^n\mu(x)\sum_{i=1}^{n/dx}\sum_{j=i+1}^{n/dx} a_{idx}a_{jdx} ixjx\\ =\sum_{d=1}^n d \sum_{x=1}^n\mu(x)x^2 \sum_{i=1}^{n/dx}\sum_{j=i+1}^{n/dx} a_{idx}a_{jdx} ij\\ T=dx =\sum_{T=1}^n T \sum_{x|T}\mu(x)x \sum_{i=1}^{n/T}\sum_{j=i+1}^{n/T} a_{iT}a_{jT} ij

avatar
zc
2020-06-04 19:43:00
查看原题

点击跳转

先了解[WC2011]最大XOR和路径的做法

线段树分治+并查集+线性基

加边删边可以用按秩合并的并查集解决,遇到环就插入线性基

由于并查集无法删除元素,删边可以用线段树分治处理(转化为每条边在一个时间段存在)

avatar
zc
2020-06-04 12:21:00
查看原题

点击跳转

[WC2011]最大XOR和路径

avatar
zc
2020-06-04 07:29:00
查看原题

点击跳转

做这题之前可以看看[WC201]最大XOR和路径

可以考虑换个思路:

对于每一对点的每一位,有多少种方案能使该位的xor和为1

dfs求出1到各点x的任意一条简单路径xord_x,那么求xy的简单路径长度就是d_x ~ xor ~ d_y

dfs的过程中也可以顺便求出所有环的xor和,这些可以用来增广简单路径,我们将这些环的xor和插入到线性基中

若线性基中有cnt个非零位,则一共会产生2^{cnt}个不同的xor

到了这一步,通过枚举两个点来统计路径的复杂度仍然是O(n^2 \cdot 60)的,我们要采用更高效的方法

直接讨论d_x对答案的贡献

先统计出第k位为0的数的个数,我们将其记为x,再统计出第k位为1的数的个数,记为y,总共有point个点

  1. d_x的第k位为1,线性基中有第k位为1的数: 此时我们有两种选择:

    • 选线性基中的,另一个点选择第k位为0的。
    • 不选线性基中的,另一个点选择第k位为1的。总体对于答案的贡献为:2^k\cdot 2^{cnt-1}\cdot (point-1),减1就是为了把自己给去掉。
  2. d_i的第k位为1,线性基中没有第k位为1的数: 这个时候另一个点只能取第k位为0的,, 所以总贡献为: 2^k\cdot 2^{cnt}\cdot x

  3. d_i的第k位为0,线性基中有第k位为1的数: 一样的,, 两种选择:

    • 选线性基中的,另一个点选择第k位为0的。
    • 不选线性基中的,另一个点选择第k位为1的。总贡献为: 2^k\cdot2^{cnt-1}\cdot(point-1)
  4. d_i的第k位为0,线性基中没有第k位为1的数: 另一个点只能取第k位为1的,总贡献: 2^k\cdot 2^{cnt}\cdot y

avatar
zc
2020-06-03 13:53:00
查看原题

点击跳转

线性基中每个元素的异或方案唯一,也就是说,线性基中不同的异或组合异或出的数都是不一样的。

那么我们把字符串转成二进制,然后插入线性基

线性基内的元素都是由外界元素异或出来的,那么对于线性基内每个元素,我们都有选/不选两种情况,

假设线性基内有cnt个元素,答案就是2^{cnt}

avatar
zc
2020-06-03 12:34:00
查看原题

点击跳转

线性基搬到了树上

线性基是支持合并的

这题就是倍增暴力合并线性基

虽然O(\log^3_2n)的复杂度已经可以通过了,但是还有更优的方法

在倍增找出询问两点的lca,然后以rmq的方式合并+查询线性基,可以将复杂度降到O(\log^2_2n)

avatar
zc
2020-06-02 13:14:00
查看原题

点击跳转

(以下长度定义为边权异或和)

首先钦定一条1到n的路径

容易发现可以通过环来增广路径

路径到环中间的路程要走两次,相当于没有

那么把所有环的长度插入线性基,

直接随意找一条1到n的路径,然后求这条路径长度在线性基上最大能异或成多少即可

假设1到n有一条更好的路径,那么会和刚才钦定的路径形成一个环,相当于异或时已经考虑过了

avatar
zc
2020-06-01 19:50:00
查看原题

点击跳转

先按魔法值排序,然后按顺序插入,如果不能被当前集合异或出来,那么插入并加上其贡献

avatar
zc
2020-05-29 17:09:00
查看原题

点击跳转

40%的log n做法挺容易的,就是一直往右儿子走,走到叶子就往左走,一直重复即可

100%的做法:

首先可以把f(l)\bigoplus\dots\bigoplus f(r)变成

[f(1)\bigoplus f(2)\bigoplus\dots\bigoplus f(r)]\bigoplus[f(1)\bigoplus f(2)\bigoplus\dots\bigoplus f(l-1)]

显然f(2^k)=f(2^k+1)=2^{k+1}-1

接着可以发现\forall k,1\le t\le 2^k-1,f(2^k+2t)=f(2^k+2t+1)

因为最下一层没有填满整一层,只填满了根节点的左子树,根节点的右子树并没有发生变化

剩下的f(n)就需要考虑一下了

首先算出树的深度(根节点深度为0)

左边: 即使没占满也全算

右边: f(n/2)

16/73
Search
search