Cumulative Sum 题意 题解 part1 \(n\) 很大,但 \(m,k\) 很小，这提示了我们。 把 \(f(x,y)\) 看成若干个关于 \(x\) 的多项式，\(f_y(x)\) 。 显然 \(y=0\) 时 \(f_y(x)\) 是一个 \(k\) 次多项式。 考虑由于 \(f_y(x)\leftarrow f_y(x-1)+f_{y-1}(x)\) 。 显然 \(f_y(x)\) 本质上 2021-09-12 数学 拉格朗日插值
daily 🌃2021 8 19 今天开始上网课了，可能事情会好起来了。 颓了好久。 没干什么正经事。 自己思维能力看起来真的不容乐观。 重要事情就留给明天吧。 🌃2021 8 20 确定了，并不是要否定自己初中的的学习方法，但也要改变初三末期对学习的看法。 「悔相道之不察兮，延伫乎吾将反。回朕车以复路兮，及行迷之未远。」 现在看来写作业应该是学好习的必要条件。 真正的成功不是逃避自己 2021-09-10
Connectivity 2 题意 Link 题解 比较有趣。 如果从单纯的做题角度，这个题似乎就没有那么有趣了，对我而言。 大意，给你个图，每条边都可以保留或切断，问有多少种方式，使得最终 \(1,k\) 联通。 \(n\leq 17\) 很容易想到bitmask(状压)。 如果对于边的状压，不好处理连通性，也有太多状态。 那么就从连通性直接状压。 \(f(S)\) 表示提取 \(S\) 点集，在 2021-09-03 数学 idea题 bitmask
Coprime Solitaire 现在很晚了，但是这个神必题卡了我真的好久好久。。。。。(before noi until present)......... （你可以通过我被这个SB题卡发现我真是个菜B) 题意 题解 显然 naive 的连边，如果 \(\gcd(a_i,a_j)\),\(a_i \rightarrow b_j\) 那么如果选 \(a_i\) 必须不能选 \(a_j\) ,显然应该选 \(b_j\) 。 2021-08-31 数学 分解质因数 2-sat
bzoj5348 题意： 你有一个随机数生成器，最初给定一个 \(0\leq x\leq n-1\) 的整数作为随机种子. 这个随机数生成器会每次输出 \(x\) 并将 \(x^k \bmod n\) 作为新的 \(x\)。 你很快发现这个随机数生成器很渣。为了证明它很渣，你想要求出有多少个随机种子，使得这个随机数生成器会输出初始种子无穷多次。 2021-08-06 数学 数论 pollard-rho 阶
arc122D 题意 Link sol 贪心思路显然，我们先把选一定没事的放在后面，接下来化归成子问题。 什么时候选一定没事，也就是 \(a_i\) 具有一个质因子 \(p\),使得 \(p\) 在 \(a_i\) 中次数最高。 形式化表示：设 \(a_i=\prod_{k}p_k^{\alpha_{i,k}}\)。 那么 \(a_i\) 选一定没事，当且仅当 存在 \(k\) , \(\fora 2021-08-05 数学 数论
arc116E 题意 Link 题解 答案显然具有单调性。 二分，对于 \(mid\) 我们计算最少需要几个点使得可以全部覆盖整个树。 我们有一个显然的贪心，对于以 \(u\) 为跟的子树，我们选 \(u\) 当且仅当子树内最深的到 \(u\) 的距离恰好为 \(mid\)。 如何证明？ 考虑如果不是这样，我们找到最深的一个选的 \(u\) 不满足上述贪心策略。 跳 \(u\) 父亲， 2021-08-04 贪心 binary search idea题 greedy