浅谈FWT 置顶 | 发表于 2018-12-24 | 评论数: § 1 前言对于离散卷积式 \begin{align} c_n=\sum\limits_{i+j=n}a_ib_j \end{align}我们可以直接使用 $\rm FFT$ 求解。 考虑该问题的扩展,如何求解将 $i+j=n$ 限制中的 $+$ 换成其他运算符的卷积式。 对于 $c_n=\sum\ ... 阅读全文 »
浅谈多项式 置顶 | 发表于 2018-12-24 | 评论数: § 1 多项式基本操作 多项式乘法 多项式求逆 多项式除法/取模 多项式开根 多项式 $\ln$ 多项式 $\exp$ 多项式 $k$ 次幂 为简化运算,所有操作均在 ${\rm mod}\ 998244353$ 意义下进行。实现时注意清空高次系数。 代码中出现的常量、变量及函数定义如下: 123 ... 阅读全文 »
浅谈分治FFT 置顶 | 发表于 2018-12-20 | 评论数: § 1 例题一=> luogu 4721 【模板】分治 FFT§ 1.1 题意给定长度为 $n-1$ 的数组 $g[1],\ g[2],\cdots,g[n-1]$,求 $f[0],\ f[1],\cdots,\ f[n-1]$,其中 \begin{align} f[i]=\sum\limi ... 阅读全文 »
浅谈动态DP 置顶 | 发表于 2018-12-07 | 更新于 2018-12-20 | 评论数: § 1 前言本文大量参考 txc 巨爷的《基于变换合并的树上动态DP的链分治算法和全局平衡二叉树学习笔记》一文。在某些问题中,我们需要实现对某种 DP 的权值修改,以及快速询问全局或子结构的 DP 值。 如果我们能找到一种满足结合律的运算来描述转移过程的话,就可以用数据结构维护合并,降低复杂度。 ... 阅读全文 »
Elysion ~楽園幻想物語組曲~ 歌词+罗马音 发表于 2019-07-11 | 更新于 2019-07-21 | 评论数: 1. エルの楽园(→side: E→)私watashiはha…生涯shougai彼女kanojoをwo愛aiすsuるruこkoとtoはhaなnaいiだdaろroうuしshiかkaしshi…彼女kanojoとtoいiうu存在sonzaiはha…私watashiにniとtoってtte ... 阅读全文 »
[EZOI][1225NOI模拟赛]farmer(树链剖分+线段树) 发表于 2018-12-26 | 评论数: § 1 题意给定一棵有 $n$ 个节点二叉树的第 $i$ 个节点的权值 $a_i$ 以及左右儿子编号(若不存在则为 $0$)。 给出 $m$ 次操作,每次操作均为以下 $3$ 种之一: $1\ u\ v$:将节点 $u$ 的权值修改为 $v$。 $2\ u$:将节点 $u$ 及其子树内所有点的左 ... 阅读全文 »
[EZOI][1225NOI模拟赛]operation(差分+前缀和+hash) 发表于 2018-12-26 | 评论数: § 1 题意给出一个长度为 $n$ 的 $01$ 序列以及一个正整数 $k$,有 $m$ 次询问,每次给出一个区间 $[l,r]$,你可以进行若干次操作,每次选择 $[l,r]$ 的一个长度为 $k$ 的子区间,将子区间上的所有元素取反,询问至少需要多少次操作才能将 $[l,r]$ 内所有元素变成 ... 阅读全文 »
[EZOI][1217NOI模拟赛]math(生成函数+分治FFT+高精度) 发表于 2018-12-19 | 评论数: § 1 题意对于集合 $S$,定义 $P(S)=\prod\limits_{x\in S}x$,即 $S$ 中元素之积。特别地,定义 $P(\emptyset)=1$。 记 $[n]=\lbrace 1,2,3,\cdots,n \rbrace$,对于 $n \in \mathbb{Z},\ 0\ ... 阅读全文 »
[EZOI][1217NOI模拟赛]set(组合数学) 发表于 2018-12-18 | 更新于 2018-12-19 | 评论数: § 1 题意记 $[n]=\lbrace 1,2,3,\cdots,n \rbrace$,对于集合 $S$ 定义 $\min S=\min\limits_{x\in S}x,\ \ F(S)=T^{\min S}$。 给出 $n,\ m,\ T$,求 $E(F(S)\ |\ S\subseteq ... 阅读全文 »
[EZOI][1215NOI模拟赛]树(树形DP+贪心+枚举) 发表于 2018-12-17 | 更新于 2018-12-19 | 评论数: § 1 题意给出三棵节点分别为 $n1,\ n2,\ n3$ 的树,再连两条边可构成一棵新树。 求可能形成的新树中,所有点对距离和的最大值。 $n1,\ n2,\ n3\leq 100000$。 § 2 分析对于其中一棵大小为 $n$ 的树,令 $dis_i$ 表示点 $i$ 到其他所有点的距离 ... 阅读全文 »