zcmimi's blog

arrow_back图论共19篇文章

avatar
zc
2020-09-29 12:40:52

查看原题

点击跳转

s_i为每个连通块点数

对每个连通块构建prufer序列

由于度数为边数两倍,\displaystyle \sum_{i=1}^k d_i=2k-2

对于给定d序列构造prufer序列的方案数为:

\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1} = \frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdot(d_k-1)!}

对于第i个连通块,它的连接方式有s_i^{d_i}种,对于给定d序列使图连通的方案数为:

\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}

枚举d序列:

\displaystyle \sum_{d_i\ge 1,\sum d_i=2k-2} {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}

换元,设e_i=d_i-1:

\displaystyle \sum_{e_i\ge 0,\sum e_i=k-2} {k-2\choose e_1,e_2,\dots,e_k}\cdot \prod_{i=1}^k s_i^{e_i+1}

根据多元二项式定理:

\displaystyle (x_1+x_2+\dots+x_m)^p=\sum_{c_i\ge 0,\sum c_i=p} {p\choose c_1,c_2,\dots,c_m}\cdot \prod_{i=1}^m x_i^{c_i}

原式化简得:

\displaystyle (s_1+s_2+\dots+s_k)^{k-2}\cdot \prod_{i=1}^k s_i

\displaystyle n^{k-2} \cdot \prod_{i=1}^k s_i

avatar
zc
2020-09-18 14:08:00
查看原题

点击跳转

传统解法

暴力的思路是求出k个点两两之间最短路径

我们可以按二进制逐位对k个点染色(该位为1染为黑色,否则染为白色)

每次求出黑点到白点的最短距离,更新答案

这样可以保证k点中每对点 至少有一次被分别染色为黑和白

复杂度n \log n \log k

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-02 13:14:00
查看原题

点击跳转

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

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

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

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

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

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

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

avatar
zc
2020-04-28 00:27:00
查看原题

点击跳转

首先把连接所有i\rightarrow p_i,可以得到若干个环

kp_i=p_{p_i}后会让i指向环上从i数起的k+1个点

只需要让一个环满足条件既可以,我们可以对每个环分别处理,然后答案取\min

可以发现假设一个环长度为l,若k可行,那么\gcd(k,l)也是可行的

我们判断是否存在0\le t < \gcd(k,l),使环上所有模\gcd(k,l)等于t的点的颜色都相同就可以了

avatar
zc
2020-04-26 21:16:00
查看原题

点击跳转

首先我们可以只保留每个数奇数次幂的因子

第二,根据约数个数定理,因为每个数的约数不超过7,所以最多只有两个质因子

可以把选择一个数看成在这两个质因子之间的连边

如果只有一个,那么把1作为另一个质因子

于是我们得到一张图

乘积为完全平方,也就是每个质因子都是偶数次幂,那么再最终的图中它的入度为偶数

那就是说我们要找这个无向图中的最小环

avatar
zc
2020-01-19 12:25:00
查看原题

点击跳转

直接按照规则建图后跑最短路

avatar
zcmimi
2019-01-21 18:36:18

LG 3953 逛公园

题意: 求dis(1,n)<=MinDis(1,n)+K的路径数

用拓扑啊什么的一想就很麻烦。

有一种玄学的做法:记忆化搜索

f[x][k]表示dis(x,n)<=MinDis(x,n)+k的路径数。

先跑一般反向的最短路,然后dfs

考虑边(x,y,w),

\because Mindis[x]-Mindis[y]+w<k

\therefore f[x][k]+=f[y][k-(Mindis[x]-Mindis[y]+w)]

\therefore f[x][k] = \sum f[y][k-(Mindis[x]-Mindis[y]+w)]

2/2
Search
search