https://codeforces.com/contest/1762
交互题
有 [0…n-1] 的排列 固定但是隐藏
你最多 2n 次询问, 找到2个下标, 其中一个要是0的下标
每次可以询问 gcd(a[i],a[j]), i!=j
n 2e4
3s
256mb
筛出 2的倍数
筛出 4的倍数
这样下去就可以了
但 次数无法保证
要找2的倍数 首先得找到一个是2的倍数的, 这最坏需要 n/2 + 3 次, 再找 就需要 n - 4 次
https://codeforces.com/contest/1766
n 点 m边 网络求一个最大流,最小费用 方案
且满足每条边上 实际流 与 其容量 奇偶性一致
输出方案, 或不存在
n 100
m 200
容量 [1,100]
单位代价 wi [-100,100]
想着把奇数处理掉, 剩下就是容量处以2, 费用乘以2的问题了
但不会处理奇数, 想到可以每个点出度入度, 但具体也不会
https://atcoder.jp/contests/abc281/tasks
问 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
六边形地图
(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!}$