https://codeforces.com/contest/1749

F. Distance to the Path

给一定n点树, 初始每个点的值为0

m 个询问, 两种操作

1. 输出点v的值
2. 对所有到路径u..v 距离小于d的点 +k

范围

n 2e5

m 2e5

d [0,20]

k [1,1000]

4s

512mb

我的思路

如果 d = 0, 就是每次对路径上的点 增加k

似乎可以树上差分+lca维护?

但实际上 中间穿插着求一个点的值, 这样每次求值还是 O(dep[u]), 并不可行

怎么有点 树链剖分的味道?

树链剖分+线段树维护每个链???

那么 d != 0 ??

似乎会变成菊花状

https://codeforces.com/contest/1783

F. Double Sort II

给你两个 1~n的排列a,b

每次操作可以任选一个i, 交换 a[i] 和 a[?]=i, 交换 b[i] 和 b[?]=i

求最小操作次数 的一个具体方案 让 a,b 有序

范围

n 3000

2s

512mb

我的思路

又是排列问题, 排列的交换就是和 i -> a[i] 建立的环相关, 每次交换不同的值,环变化都是1(+1/-1),

如果单独看 a,

每次只要不是操作 swap(ai,ai), 都是 环+1

所以问题变成:

找尽量少的 下标集合, 使得a,b 中的 环中被选中的个数 >= 所在环点的个数-1

3000 似乎希望n^2 的样子

考虑 如果把一个变有序

(x-x-x-x) (x-x-x) ...

另一个怎么转移

1
2

a: 1-2 3-4 5-6-7-8
b: 1-2-3-4 5-6 7-8

https://atcoder.jp/contests/abc284/tasks

Ex - Count Unlabeled Graphs

按照下面步骤生成图

选 简单,无向,n个无标签点 的图

给每个点 写 <= k的数, (1~k每个都至少出现一次

找方案数 mod p(质数 1e8~1e9)

范围

k <= n <= 30

我的思路

无标签的图 和 有标签的图之间 如何进行 重复统计的转化 ???

考虑按照连通块来划分

连通块大小 和 同联通块大小的选择个数

f[s] = 每个连通块大小为s 的 染色方案数 的生成方程 = a[s] x^s + a[2s] x^2s + a[3s] x^3s …

为了统计 g[s] = 加上外部贡献的选择倍数 = a[s]/s! x^s + a[2s]/(2s)! x^2s + a[3s]/(3s)! x^3s …

这样 ans = [x^n] n! g[1] * g[2] * g[3] * ... * g[n]

那么问题来了, 如何计算f[i]

h[i] = 1个大小为i的联通块的染色方案数

a[i] = h[i], 直接染色

a[2i] = binom(2i,i-1) h[i] * h[i], 确定1在地一个块

a[3i] = binom(3i,i-1) * binom(2i,i-1) h[i]^3, 确定1在地一个块, 不在第一个块中最小的在第二个块

那么如何计算h[i]

count[形状] = 一个形状的染色方案数

h[i] = sum count[形状i]

形状不同, 染色后一定不同, 但是相同形状 染色后可能相同,

如何判断两个形状不同, 如何枚举形状, 每个形状如何计算染色方案??????????????????????????

并不会

能想到一些必要条件, 但没啥充分条件, 比如 点i连的点和相同,且度相同

第一类stirling数

$s(n,k) = \begin{bmatrix} n \\ m \\ \end{bmatrix}$ 表示n个不同元素, 划分成m个非空段(每个非空段 满足循环平移等价) 的方案数

(n个两两不同元素,划分为k个互不区分的非空轮换的方案数, 也就是 如果划分出 [1,2,3] 那么 和[2,3,1]等价和[3,1,2]等价, 但是和[3,2,1]等价

$\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}$ 一样的也是考虑 最后一个单独放还是插入到前面某个序列里

边界$\begin{bmatrix}n\\ 0\end{bmatrix}=[n=0]$

生成函数

构造生成函数 $F_n(x)=\sum\limits_{i=0}^n\begin{bmatrix}n\\ i\end{bmatrix}x^i$

根据递推公式$F_n(x)=(n-1)F_{n-1}(x)+xF_{n-1}(x)$

有 $F_n(x)=\prod\limits_{i=0}^{n-1}(x+i)=\dfrac{(x+n-1)!}{(x-1)!}$

https://atcoder.jp/contests/abc283/tasks

Ex - Popcount Sum

$0 \le R,M+R,2M+R,3M+R,\cdots < N$

$R \in [0,M]$

问上述[0,N]中的这些数, 的二进制下的1的个数的总数

范围

t 组数据 1e5

n 1e9

4s

1024mb

我的思路

分类一下, 感觉就需要一点数学, 然后t 1e5, 基本也就是说, 要么O 1,要么O sqrt 左右

如果m==1, 那么就是1…n 的所有数的二进制1的个数和, [1…2^t,2^t+1…n] 这样划分就是 sqrt

如果m==2^k, 那么这些数的 低k位都一样, k位以上, 和上面是一样的

如果m 不是上面的情况,进位的时刻, 似乎并不好拿捏

2, 3+2,6+2,9+2

1
2
3
4
5

  10
 101
1000
1011
1110

能说的是 低两位4次的循环节, 比3还大, 高位也没啥规律

对称相加

R, M+R, 2M+R, … , kM+R

kM+R, (k-1)M+R,…, R

对称的和始终是 (k+1)M+R, 有办法 只算 一半 与 (k+1)M+R 的bit的联系, 这样一半