牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共30篇）

省选模拟87 题解

A. a 直接构造一个简单的生成函数，就转化为求 $A^n(x)$ 的前 $x$ 项系数。一个很神奇的解决多项式 $A^n(x)$ 前 $n$ 项系数的做法。复杂度为 $O(nk)$，其中 $k$ 为 $A(x)$ 的项数。做法是这样的，对 $A^{n+1}(x)$ 分别用乘法 $A(...

网络流构造题二分图多项式

2020-05-04

0 402

省选模拟96 题解

A. 多边形因为本题保证了 \(n\) 不为偶数，所以 \(n\) 没有 \(\frac{n}{2}\) 这个循环节。然后考虑 \(\frac{n}{3}\) 这个循环节，如果能形成锐角一定有 \(m=3\)。如果存在更小的循环节，那么一定不存在锐角了。所以尽量特殊处理一下 \(m=3\) ...

多项式 trie树

2020-05-14

0 372

noi前第九场题解

A. s1mple 可以发现 0/1 这个限制类似于求路径数，使得路径经过的边权恰好合法。显然可以用容斥来求，这样可以将问题转化为钦定其中若干条边权为 \(1\)，其他边权任意的路径数。这样做有一个好处，原来问题中的 \(2^{n-1}\) 的集合可以缩减状态数。对于钦定之后的若干条 \(1...

dp 多项式后缀自动机拉格朗日插值启发式合并状压字符串

2020-07-21

0 379

noi前第十场题解

A. 集合划分可以直接写出一个简单的 \(dp\)，然后发现这个 \(dp\) 的信息只需要存 \(A\) 集合选的个数和末尾选的哪个集合。不妨写成一个多项式，那么我们只关心边界的情况。所以写一个分治 \(FFT\) 即可。 B. ACT4！⽆限回转！考虑对于每条边，枚举所有能到达...

计算几何分治多项式 dp 辛普森积分

2020-07-22

0 405

noi前第十一场题解

##A. 数容易发现答案是 \(f_m=\sum \limits_{i=0}^n a_i[x^i](1-x)^m(1+x)^{n-m}\) 然后就有一个显然的 \(O(n^2)\) 做法，并不会优化。一个优化的方法是，考虑 \((1-x)\) 和 \((1+x)\) 相加为 $2$。所以可以将...

组合计数计算几何多项式 dp

2020-07-24

0 501

noi前第十二场题解

A. string 对于这类字符串匹配题，有个套路是直接用 \(FFT\) 优化。然后发现这题字符集很小，所以枚举一个字符，将匹配串中的这个字符设为 \(1\)，模式串中的非这个字符设为 \(1\)。然后用一些技巧优化一下，就可以用 \(|\sum|+1\) 次长度为 \(n\) 的 \(DF...

平衡树多项式 trie树 dp 字符串

2020-07-25

0 553

noi前第十四场题解

A. ⼩W数排列做过类似的题，思路大概将所有数从大到小插入。这样相邻两个位置的贡献就转化为一加一减。可是这样做会导致值域变得很大，其实这样没用到题中 \(l\) 很小的限制。考虑这样一个做法，把每次一加一减的贡献差分掉。每次基准线降低的时候直接统计降低的高度*降低的个数的贡献。因...

dp 多项式生成函数线段树

2020-07-28

0 503

noi前第十八场题解

##A. 林海的密码难点主要就是如何构造加法操作。一个点数 $2 \log n$，边数 $5 \log n$ 的做法是这样的。像这样构造一个双向的环，显然一个内向生成树为断掉红边的后缀、黑边的前缀。发现这样每次只能使贡献 \(*2\) 或者不变，所以问题就是用若干个连续的 $2$ 的次幂...

构造题分治二项式反演多项式容斥

2020-08-02

0 601

<span>noi前第十九场题解</span>

##A. 欢迎来到塞莱斯特山容易想到对每个联通段进行 \(dp\)。这样在归并子树的过程中只需要枚举两者分别的段数，枚举合并成多少段。转移系数只要做一个 \(O(n^3)\) 的 \(dp\) 就可以预处理出来。复杂度大概就是子树归并的复杂度 * \(n\)，写个指针卡卡内存就能过了。 &n...

线段树分治多项式 dp

2020-08-03

0 493

拉格朗日反演

拉格朗日反演及扩展拉格朗日反演如果有 \(F(G(x))=x\)，即 \(F,G\) 互为复合逆，同时一定有 \(G(F(x))=x\)，可以称 \(G(x)=F^{-1}(x),F(x)=G^{-1}(x)\)。在这种情况下，有这样的式子：拉格朗日反演 \[[x^n]F(x)=...

多项式

2020-09-08

0 617