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!}$
https://codeforces.com/contest/1764
给 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
给定正整数, 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
https://codeforces.com/contest/1761
f(x,y) = g(x)+g(y)-g(x+y)
其中g(x) = x二进制下的bit为1的个数
问 $f(x,y) = k$ 有多少个, 其中 $x,y \in [0,2^n)$, 答案mod 1e9+7
n < 1e6
1s
256mb
打了表
1 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
推了个 多项式的矩阵幂次, 然而 赛后才知道, 1e9+7 就是不希你用ntt因为原根极小等于没有
1 | (1,0) |