51nod1355 斐波那契的最小公倍数
51nod LOJ 分析 为了方便，下面简记 $f_S$ 为 $f_{a_1},f_{a_2},\cdots,f_{a_k}$，其中 $S=\{a_1,a_2,\cdots,a_k\}$。 考虑一个经典容斥 从小到大枚举倍数算贡献即可。 实现得好的话时间复杂度是 $\mathcal{O}(n\log n)$ 的。 代码 // ================================...
分类 题解 下的文章
- 首页
- 题解
洛谷3700 [CQOI2017]小Q的表格
Luogu LOJ 分析 可以发现这两条规则长得很像更相减损术，推一推可以得到 最后那一步可以考虑实际意义，证明就不写了（ 如果没有修改的话就可以预处理 $i^2\varphi(i)$ 的前缀和然后数论分块计算了。然而现在还有若干次对于 $f(d,d)$ 的修改，可以想到用一个数据结构来维护。 思考一下，我们在数论分块时需要进行 $\mathcal{O}(Q)$ 次修改和求 $\mathc...
洛谷3312 [SDOI2014]数表
Luogu LOJ 分析 先不考虑 $a$ 的限制，则答案为 这样子可以发现，我们只要把 $\leq a$ 的 $\sigma(k)$ 的贡献设成 $\sigma(k)$、$> a$ 的 $\sigma(k)$ 的贡献设为 $0$ 就可以算出正确答案了。 于是只要把所有询问按 $a$ 排序，然后将 $\sigma(k)$ 从小到大加入即可。 代码 // ===============...
洛谷3704 [SDOI2017]数字表格
Luogu LOJ 分析 下面都假设 $n\leq m$。 方法一 推出来和上面是一样的。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include &...
洛谷3517 [POI2011]WYK-Plot
Luogu LOJ 分析 首先要会最小圆覆盖而且知道它是期望 $\mathcal{O}(n)$ 的。 显然可以二分答案，于是我们只要想办法判定能否分成最小圆覆盖半径都 $\leq mid$ 的 $\leq m$ 段即可。 显然最小圆覆盖半径是随着点的增多而不降的，所以每段的点越多越好。于是可以想到暴力找每段的右端点，然而可以卡成 $\mathcal{O}(n^2)$。还有一个想法是二分右端点...
洛谷4491 [HAOI2018]染色
Luogu LOJ 分析 显然一块画布上出现次数为 $S$ 的颜色不超过 $L=\min\left\{m,\left\lfloor\frac{n}{S}\right\rfloor\right\}$ 种。 考虑容斥。设 $f_i$ 为出现次数为 $S$ 的颜色有至少 $i$ 种的方案数，不难得到 可以发现是一个差卷积的形式，于是直接 NTT 即可。 代码 // ===============...
洛谷4451 [国家集训队]整数的lqp拆分
Luogu 分析 设 $g_n$ 为 $n$ 的答案，则 我们只需要求 $[x^n]G(x)$，即 $\frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}}$，而 $2$ 在模 $10^9+7$ 意义下是有二次剩余的，所以直接计算即可。 代码 // ==================================== // author: M...
CF438E The Child and Binary Tree
Codeforces Luogu 分析 设 $s_i$ 表示 $i$ 是否在集合中，$f_i$ 表示权值和为 $i$ 的二叉树数量，那么 多项式开根+多项式求逆即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =========...
洛谷4841 [集训队作业2013]城市规划
Luogu 分析 设 $f_i$ 为 $i$ 个点的无向连通图个数，$g_i$ 为 $i$ 个点的无向图个数，那么显然有 多项式求逆后卷起来求出 $[x^{n-1}]F(x)$ 从而求出 $f_n$ 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-bl...
洛谷4459 [BJOI2018]双人猜数游戏
Luogu LOJ 分析 下面的 $n,m$ 和题面上是反的（因为我写完才发现这个问题所以就懒得改了）。 先复原一下样例一（$s=5,nm=60,n+m=16$）的游戏过程中双方的心理活动。 Bob：$(n,m)$ 的可能情况有 $(5,11),(6,10),(7,9),(8,8)$，所以回答不知道。 Alice：$(n,m)$ 的可能情况有 $(5,12),(6,10)$，两种情况 Bo...