牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共241篇）

拉格朗日反演

拉格朗日反演及扩展拉格朗日反演如果有 \(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

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

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

线段树分治多项式 dp

2020-08-03

0 493

noi前第十八场题解

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

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

2020-08-02

0 601

noi前第十七场题解

##A. 黑白沙漠考虑这样一个做法，对于每个点处理出左侧和右侧分别的最优决策点，然后比较二者谁更优即可。当然这样的点可以表示为若干个区间，对于其中每个区间，左右侧谁更优是单调的，可以通过二分求解。所以问题就是如何处理出这样的若干个区间。可以想到这个最优决策点就是上凸包会切到的点。所以写一...

网络流凸包分治单调栈线性规划

2020-08-02

0 555

noi前第十六场题解

##A. 小B的班级莫名想到了一个结论，这种题可以找到选中的点形成的重心。然后求所有点与重心距离的和即可。原因是，任意一个子树大小均小于 \(m\)，所以总可以构造出方案。在这道题中，只要枚举最接近 $1$ 号点的可能的重心，然后计算方案数就可以 \(O(n^3)\)。仔细想一下，可以把...

线段树分治单调栈 KMP 字符串

2020-07-30

0 518

noi前第十五场题解

##A. zsy家今天的饭对于 \(\binom{m}{k}\) 种方案，答案是跨过的边权*2-直径。可以对两部分分别计算贡献。对于前者，可以考虑计算每条边的贡献。若将餐厅点集划分为 \(a,b\) 两部分，那么乘上的系数就是 \(\binom{m}{k}-\binom{a}{k}-\bi...

长链剖分博弈论 dp

2020-07-29

0 490

noi前第十四场题解

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

dp 多项式生成函数线段树

2020-07-28

0 503

noi前第十三场题解

A. 钩子可以发现大概问题是一层一层的。对于每一层，一定会选完所有长度为 \(2x,2x-1\) 的连续段之后递归下一段。可以考虑将这样的选择合并在一起考虑，然后做一个 \(dp\)。可以发现概率的大小大概只与剩下的奇数、偶数段的个数有关，所以记录奇数段的个数就可以转移了。然后的问题是怎...

ETT 分治 dp

2020-07-27

0 443

noi前第十二场题解

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

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

2020-07-25

0 553

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