搜索结果
查询Tags标签： operatorname，共有 22条记录-
OI中的一些数学小技巧
在OI比赛中，如果能够灵活地运用一些数学小技巧，是能够很好地优化计算的时间和正确性的。 既然说了是小技巧，那么这些指的都是一些技巧，一般是不会单独成题的。 光速幂 有的时候，我们要去求解一个数或者一个矩阵的若干次幂，而这个指数在一般情况下是暴力无法接受的，…
2022/8/25 23:26:20 人评论 次浏览 -
「NOI2020」超现实树
题目 点这里看题目。 分析 困难的题目。 思路一 从命题逻辑的角度考察一棵树的限制。 某棵树的 \(\operatorname{grow}\) 可以被写作树上结点存在性（在或不在）的合取。考察 \(\operatorname{grow}\) 的并的时候，出于方便运算的考虑可以取补集，于是就变成了析取范式的合…
2022/8/2 23:22:46 人评论 次浏览 -
Hash——温暖人心的算法
目录简介计算Hash前缀Hash递推快速计算子串Hash用Hash匹配字符串综合：P2852 [USACO06DEC]Milk Patterns G 简介 Hash，将一个字符串映射到一个数字上。 计算Hash 计算Hash的方法有很多种，比如说在密码学中常用的 \(\texttt{MD5}\) 和 \(\texttt{SHA256}\) 等。 但是我们…
2022/7/28 1:23:58 人评论 次浏览 -
有向图最短偶环的多项式算法 (Bj?rklund, Husfeldt, Kaski, 2022)
本文将对 STOC2022 的一篇论文: "The shortest even cycle problem is tractable" 进行解读. 虽然这是一篇很新的文章, 但是其核心技术还是相当通俗易懂的. 下文讨论的皆为无权图, 或者说, 环的长度就是经过的点的数目. 我们知道, 最短奇环是容易解决的, 因为最…
2022/7/4 14:21:34 人评论 次浏览 -
排列 题解
题面 给定一个长度为4的排列a与一个长度为n的排列b。在b中选出长度为4的子序列使该子序列与排列a的相对顺序相同。输出选法个数。共24个subtask，意即所有排列都会出现。$ n \le 2000。 $ 解法 我们考虑将这个排列a划分成两个互不相关的部分。两个部分互不相关，当且仅当他…
2022/6/29 23:26:04 人评论 次浏览 -
SD
D1T1 树形 \(\text{DP}\)。 令 \(f_{u,s,k},(k\in\{0,1\})\) 表示仅考虑以点 \(u\) 为根的子树，固定 \(u\) 的权值为 \(s\)，\(u\) 子树中是否有点的权比 \(u\) 的权大的方案数。 \[\begin{aligned}\\ f_{u,s,0}&=\sum_{v\in\operatorname{son}(u)}\sum_{w\in\operat…
2022/6/19 23:23:39 人评论 次浏览 -
FWT 学习笔记
快速沃尔什变换（FWT）学习笔记 What 这是啥呀 \(~~~~\) 快速沃尔什变换也用于解决一些卷积问题，所不同的是它解决的卷积的下标一般由位运算代替加法，因此也可以用集合卷积来表示其所能解决的问题。 \(~~~~\) 才疏学浅，理解不深，仅能至此。 How 怎么做 \(~~~~\) 显然暴…
2022/5/3 23:13:00 人评论 次浏览 -
整除分块 学习笔记
板子题 板子题-UVA11526 题目大意： 给定一个 \(n\)，求 \(\sum\limits_{i-1}^{n}\lfloor \frac{n}{i} \rfloor\)。其中 \(n\) 为 \(32\) 位无符号整数。 题目解析 显然如果暴力求解肯定是不可行的，显然会 TLE，所以我们需要找一种复杂度更优的算法。 我们可以先令 \(n=1…
2022/4/25 23:15:57 人评论 次浏览 -
【CF1601F】Two Sorts（Meet in Middle）
题目链接定义 \(a_{1\sim n}\) 为将 \(1\sim n\) 按字典序从小到大排序后的结果，求 \((\sum_{i=1}^n(i-a_i)\ \operatorname{mod}\ 998244353)\ \operatorname{mod}\ 10^9+7\)。 \(1\le n\le10^{12}\)题意转化 这题的求和中有两种不同的取模，看起来非常麻烦。 考虑取模的…
2022/3/8 23:19:25 人评论 次浏览 -
[CF1242B]0-1 MST 题解
CF1242B 0-1 MST传送门思路：(注：此文设题中输入的图为 \(G_1\)，对应的完全图为 \(G_2\)，对应的补图为 \(G_3\)) 首先不难想到暴力思路：直接将 \(G_2\) 建出来，跑一遍 MST 即可。 然而这样时间和空间复杂度都是 \(\operatorname{O}(N^2)\) 的，显然无法承受。 但是这…
2022/1/25 23:34:30 人评论 次浏览 -
【学习笔记】开发福利院保护（FFT）
概述 FFT，即 快速傅里叶变换 ，是将多项式乘法从 \(O(n^2)\) 优化到 \(O(n\log n)\) 的算法。 本质上是优化卷积，卷积的一般形式： \[C(i)=\sum\limits_{i\oplus j=k}A(i)B(i) \]其中多项式乘法为加法卷积，即： \[C(i)=\sum\limits_{i+j=k}A(i)B(i) \]系数表示法： 我们…
2022/1/23 23:06:30 人评论 次浏览 -
prufer序列
目录$\operatorname{prufer}$序列定义构造无根树到序列序列到无根树性质与相关结论 \(\operatorname{prufer}\)序列 定义 一种无根树上的数列。 由顶点标号的无根树转化而来。且对于一棵确定的无根树，其对应的\(\operatorname{prufer}\)序列也是唯一确定的。构造 无根树到…
2021/11/10 23:12:54 人评论 次浏览 -
prufer序列
目录$\operatorname{prufer}$序列定义构造无根树到序列序列到无根树性质与相关结论 \(\operatorname{prufer}\)序列 定义 一种无根树上的数列。 由顶点标号的无根树转化而来。且对于一棵确定的无根树，其对应的\(\operatorname{prufer}\)序列也是唯一确定的。构造 无根树到…
2021/11/10 23:12:54 人评论 次浏览 -
快速傅里叶变换FFT
目录快速傅里叶变换FFT用途前置知识系数表示法点值表示法单位负根定义性质快速傅里叶变换FFT快速傅里叶逆变换作用方法与推导 快速傅里叶变换FFT 用途 \(\operatorname{FFT}\)算法支持在\(O(n log n)\)时间内计算两个\(n\)度的多项式的乘法。也可以用来加速大整数乘法运算…
2021/11/10 23:11:04 人评论 次浏览 -
快速傅里叶变换FFT
目录快速傅里叶变换FFT用途前置知识系数表示法点值表示法单位负根定义性质快速傅里叶变换FFT快速傅里叶逆变换作用方法与推导 快速傅里叶变换FFT 用途 \(\operatorname{FFT}\)算法支持在\(O(n log n)\)时间内计算两个\(n\)度的多项式的乘法。也可以用来加速大整数乘法运算…
2021/11/10 23:11:04 人评论 次浏览
