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

G - Farthest CIty

问 n个点, 的简单连通图, 1到n的距离 严格大于所有1到其它点的距离的 图有多少个

个数 mod m

范围

n 500

m [1e8,1e9]

4s

1024mb

我的思路

数数嘛, 对于一个具体的图, 考虑计算所有点到1的距离,看一下相邻点的性质,

显然 相邻点的距离值 差不大于1

所以有一个O(n^4) 的dp

dp[最大距离为i][距离为i的有j个][距离<=i的有k个] = 的方案数

有转移 dp[i][j0][k0] = dp[i-1][j1][k1] * binom(n-k1,j0)/j0个在剩下的中选/ * (2^(j1)-1)^j0(每个分别和前面j1的连接方式) * 2^(j0(j0-1)/2) (j0个内部的任意连接) , 其中 k0=k1+j0

这样答案就是 sum dp[1..n][1][n]

要是能优化成O(n^3)就能过了, 比赛时想了半天, 发现i无关, 想说矩阵乘法快速幂次, binom拆一拆 搞了半天

---

赛后又想了想, 可以完全不要 i 直接 dp[用了k个点][最大距离的有j个点]的方案数 就完了………………..

dp[i0][j0] = dp[i1][j1] * binom(n-i1,j0) * (2^{j1}-1)^j0 * 2^(j0(j0-1)/2), 其中 i0=i1+j0

ans=dp[n][1]

其实这里有点问题, 因为中间选的时候不能选择 最后一个

所以不妨 先把 n拿出来 最后考虑它

这样转移方程不变

ans= sum dp[n-1][j=1..n-1] * (2^j-1)

---

然后加个预处理 去掉 中间的log复杂度

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

G - Do Use Hexagon Grid 2

六边形地图

(i,j) 和 (i+-1,j), (i,j+-1), (i+1,j+1) ,(i-1,j-1) 相邻

给你n个点

问有多少种方案能选一个非空点集, 使点集中两两距离不大于D

范围

n 300

xi,yi, [-1e9,1e9]

d [1,1e10]

3s

1024mb

我的思路

先想 1维, 就是sort, 然后定必定要选的点从左到右, 找区间长d中的点个数的2的幂次

然后不是六边形的 2维, 类似的定(左,下)角的点, 但问题是 其它点个数不能再2的幂次了

总觉得做过, 但是又完全不会

n=300 就可能 3次方的做法

反演

已知$f$ 使得 $\displaystyle a_n = \sum_{i=0}^{\infty} f_{n,i} \cdot b_i$

求$g$ 满足 $\displaystyle b_n = \sum_{i=0}^{\infty} g_{n,i} \cdot a_i$

有不少的 $f_{n,> n} = 0$ 所以$\infty$ 对应的替换成$n$也是同样道理

有不少文章从意义角度, 或者直接给表达式,让你验证正确性来写的, 而我没有智力, 总觉得很怪和难以理解, 这篇主要通过EGF和假设没有预知能力来写

基本理论

对于一个明确反演, $f$实际是给定的常数序列, 看成矩阵乘法有(其中$a,b$ 为列向量)

$a = M_f\cdot b$

则$b = M_f^{-1}\cdot a = M_g \cdot a$

即$M_f \cdot M_g = I$ (单位矩阵)

即$\displaystyle \sum_{k=0}^{\infty} M_{f,i,k} M_{g,k,j} = \lbrack i=j \rbrack $ 是充要条件

一般题目中 知道$a$与$f$, 需要求$b$时使用

下面一般步骤首先建立分别的EGF, 然后通过正向得到两个EGF的等价关系, 最后转换等价关系推得逆向的递推式

egf(指数形 生成 函数), 构建EGF:

$\displaystyle F(x) = \sum_{i=0}^{\infty} a_{i} \frac{x^i}{i!}$

$\displaystyle G(x) = \sum_{i=0}^{\infty} b_{i} \frac{x^i}{i!}$

https://codeforces.com/contest/1764

E. Doremy’s Number Line

给 a[1..n],b[1..n]

每次只能一种操作

把 [0,a[i]] 中某个未染色的染色为i

或者

如果 有 v <= a[i] 已经染色, 则可以把 [0,v+b[i]] 中 某个未染色的染色为 i

问 k 能否染色成 1

i的顺序 任意, 但每个i最多选一次

范围

n 1e5

k 1e9

ai,bi [1,1e9]

2s

256mb

我的思路

转换成当前最大的可达的值, a[1] 最后操作

如果前面操作了, 那么 后面的操作 按照a[i]+b[i]顺序, 不会更差

但不知道怎么处理第一个的选择, 如果第一个的值 >= 排序后的 a[first], 可以dp[n][放弃了一个 >=的 还是 没有放弃的]

但这个只能处理特殊情况的处理不了所有

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

Ex - Sum of Prod of Min

给定正整数, n,m, 保证 $m \in [n,2n]$

对所有长n 且和为m的正整数序列S, $f(S) = \prod_{i=1}^n min(i,S_i)$

输出 $\sum_S f(S) \bmod 200003$

范围

$n \in [1,10^{12}]$

2s

1024mb

我的思路

这n 是真的大

但是也还好, 因为 sqrt(n) 大概是10^6

而注意到$\min [n,2n]$

而每个数要是正数, 所以$S_i > i$ 的不会超过 $O(sqrt(n))$ 个!

dp[第c个超过] = vector{最后超过的i, 剩余 > 1的部分, 前面乘积}

这状态感觉也少不了

一个是 当前超过的是啥, 前面的乘积, 自由的状态, 剩余的未分配数

---

等一下,上面读错题了, 是min不是max