LittleFoxFairy

摘要： 钦定：考虑选 $ i $ 个条件，且只考虑这 $ i $ 个条件，即与剩下的东西选不选无关。 恰好：考虑选 $ i $ 个条件，且剩下的 $ n-i $ 个条件一定不选。 令 $ f_i $ 表示钦定，$ g_i $ 表示恰好，则有二项式反演： \[f_i = \sum\limits_{j=i}^{ 阅读全文

摘要： CF1264D Beautiful Bracket Sequence 难点在于刻画答案。 你直接考虑枚举每个括号序列最中间的那个左右括号交界的位置算答案。 考虑枚举到一个位置 $ i $，现在 $ i $ 左边有 $ l $ 个左括号，右边有 $ r $ 个右括号，左边有 $ x $ 个问号，右边有 阅读全文

摘要： 让我们来写一点 SAM 的例题。 endpos 集合大小就是这点包含的一堆子串(在原串中)的出现次数。 设 \(lcs(i,j)\) 为前缀 \(i,j\) 的最长公共后缀长度,其等于 \(parent\) 树上 \(LCA\) 的 \(len\) 值。 要找到一个子串在 SAM 中的位置，可以先记 阅读全文

摘要： 板子略过。 和 $ SAM $ 不一样，$ PAM $ 的转移边构成的图也是一棵树。 转移边定义：若 $ x $ 到 $ y $ 有一条边权为 $ c $ 的转移边，则表示 $ y = c + x + c $。 后缀链接定义：对于一个结点 $ u $ 的后缀链接 $ fa \(，\) fa $ 是 阅读全文

摘要： 令 $ f(a,b,c,n) = \sum\limits_{i=0}^n \lfloor \dfrac{ai+b}{c} \rfloor $ $ f(a,b,c,n) = \sum\limits_{i=0}^n \lfloor \dfrac{(a \bmod c)i + (a- a \bmod c) 阅读全文

该文被密码保护。 阅读全文

该文被密码保护。 阅读全文

摘要： 这个东西有点太牛了，简单写一下。 煮波数学非常烂，所以大多数东西只能感性理解。 首先格路计数，从坐标 $ (0,0) $ 走到 $ (n,m) $ 的路径方案数（只能向右或向上走）为 $ C_{n+m}^{n} $。 考虑组合意义就是你的路径总长度为 $ n+m $，一共要向右走 $ n $ 次，相 阅读全文

摘要： 数学/计数做题笔记 P4159 [SCOI2009] 迷路 矩阵快速幂优化递推。 首先最暴力的想法，设 $ f_{i,j} $ 在 $ j $ 时刻，到达点 $ i $ 的种类数。 枚举时间和 $ i $，然后 $ f_{i,j} = \sum\limits_{k=1}^n {f_{k,j-w[i] 阅读全文

摘要： 既然多头说记录技巧比较重要，那就写个记录吧，希望至少能提升点啥。 \(DP\)，如果题目要求的是求一个问题的最优解（如：完成一个任务 XXX 的最大/最小代价），设计状态时可以考虑从繁杂出发，设一个 \(bool\) 数组，表示满足状态条件是否能够完成，然后再考虑优化。(\(eg：P2224\)) 阅读全文