__故人__

随笔

CF(8) UOJ(1) 每日一题(3) 牛客小白月赛27(10) 算法模板(10) 题解(117)

/ 注册

全部文章 / 随笔（共20篇）

关于Bell的指数型生成函数推导来自专栏

必要公式首先我们知道根据第二类斯特林数和贝尔数的定义很容易证明。第二类斯特林数的通项公式，可以根据容斥定理枚举空的盒子得到。我们知道这个是在处的展开。而，因此得证。这个是最简单的二项式展开了。不多说明。推导那么现在。是不是很神奇，神奇就点个...

2020-10-10

4 944

[CH弱省胡策R2]TATT

分析可以考虑到为结尾的最长的序列。那么。所以其实这个是个四维偏序。所以我们考虑来做。时间复杂度为。但是有几个非常重要的减枝条件。可以参照代码。代码 #include<bits/stdc++.h> using namespace std; int read() { ...

2020-09-27

3 513

[国家集训队]JZPFAR

分析一次过，非常爽。考虑上的最近邻查询。虽然有人已经证明上的最近邻查询时间复杂度会被构造数据卡到。但是多数情况下是非常快的。那么这道题，只是把最近邻换成第大距离。我们只需要用个堆来动态维护一下就好了。注意因为有编号的问题，所以要注意查询的小细节。代码 #include<bi...

2020-09-26

6 521

POJ - 2976

分析找来的分数规划模板题。我们要求的是，所以直接二分，那么贪心的选取最大的个，最后再判断就好了。代码 // #include<bits/stdc++.h> #include<iostream> #include<cstdio> #inc...

2020-09-23

3 550

原根来自专栏

原根这个的用处还是非常大的在模意义下的乘法可以通过原根转换为加法。 NTT 需要原根。定义，且。则称是的一个原根。是否有原根只有，其中为奇素数，为正整数。计算最小原根这里直接使用最常见的作法。由小到大枚举。。那么只需要判断就可以了，如果有一个...

2020-09-23

1 782

rmq 问题一种 O(n) 预处理，O(1) 回答询问的方法

引入现在市面上大多数解决问题的一般是预处理，回答的线段树，平衡树。预处理，回答的表，猫树。预处理，回答的分块加表，这种神仙算法。这里考虑使用的预处理，回答的算法，这里用求区间最大举例。 Cartesian-tree 对于笛卡尔树，我们可以...

2020-09-22

2 0

HDU - 1506

分析去专门学了笛卡尔树，找了一道模板题来做。由于我们建立的笛卡尔树满足小根堆性质，因此的子树内的结点的高度都大于等于。而我们又知道子树内的下标是一段连续的区间。所以。通过单调栈构建笛卡尔树，时间复杂度为。代码 #include<bits/stdc++.h> usi...

2020-09-22

2 592

[BZOJ 3028] 食物来自专栏

分析刚学生成函数，来试试水。我们先把每一种的生成函数写出来，并转化为封闭性式。全部相乘之后。如何转化为幂级数的形式。因为所以所以最后的答案为。代码 #include<bits/stdc++.h> using namespace std; cons...

2020-09-21

3 605

[TJOI/HEOI2016] 求和来自专栏

[TJOI/HEOI2016] 求和所以我们现在可以求出了。因为后面的式子已经是卷积形式了了。代码 #include<bits/stdc++.h> using namespace std; const int p = 998244353,Gi = 3,N = 1e6 +...

2020-09-19

4 626

多项式乘法逆来自专栏

多项式乘法逆给你多项式，寻找一个多项式满足。考虑倍增求解。如果我们已知，而根据。那么显然 ,两式相减那么 ,左右相减。考虑左右都乘上一个，那么移项。那我们的递归出口为。代码 #include<bits/stdc++.h> using name...

2020-09-19

5 710