牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共33篇）

模拟105 题解

A. 小W的魔术考虑问题的逆问题，怎样的字符串是好的字符串。即长度为$n$，前缀与给定字符串的前缀匹配，后缀与给定字符串的后缀匹配的字符串个数。不妨枚举给定字符串的断开点，那么答案即$(len+1)*26^{n-len}$ 然而这里面有重复计算的方案，把它画出来就可以发现，相邻两次...

结论题 dp 倍增组合计数数位dp

2019-11-08

0 357

模拟111 题解

A. 物理课发现每次反弹之后移动的距离是上一次的$d^2$倍。计算出第一次反弹之前移动的距离的答案$k$，总的答案即$\sum \limits_{i=0}^{inf}d^{2*i}*k$。发现这个东西就是一个等比数列求和。设答案为$s$，那么有$s=\sum \limits_{i...

线段树分治并查集启发式合并组合计数

2019-11-12

0 343

模拟115 题解

A. Tiny Counting 考虑枚举$a$，可以直接用树状数组查找合法的$b$，接着直接乘逆序对个数就好了。然而这个时候就存在一些非法的状态，$b$作为逆序对出现了。所以只要再枚举一遍$b$，减掉对应的贡献就好了。 B. Medium Counting 因为...

数位dp 树状数组组合计数

2019-11-14

0 379

关于斯特林数

第一类斯特林数定义 $S_1(n,m)$表示$n$个元素，形成$m$个环的方案数，记作$\begin{bmatrix}n\\m\end{bmatrix}$。其中每个元素是不同的，每个环是相同的。递推公式从实际含义上去考虑，第一类斯特林数递推公式为： $\begin{bmat...

容斥组合计数数学斯特林数二项式反演

2019-12-11

0 428

省选模拟2 题解

A. 铁轨建设暴力插头dp+网络流判断可行性，可以拿到85分。然而这个题看起来就很像无限之环，只要稍微改一下建图就好了。然而这个建图还蛮难想到的。 B. 圈地游戏因为不会做+看不懂题解+std太长，所以咕掉了。 C. 组合数学 70分部分分：考虑到状态数很少，直接暴...

dp 网络流二项式反演容斥组合计数

2019-12-24

0 408

数学专题测试1 题解

A. 解方程考虑没有任何限制的东西， m个元素分为n个连续的区间，直接用组合数插板法就好了。考虑如何去掉元素大于$a_i$的限制，只要给最终的元素个数减掉$a_i$就好了。考虑如何搞元素个数小于$a_i$的限制，不妨使用子集反演，要求的是恰好$0$个元素大于$a_i$。只要...

容斥 lucas定理组合计数数学多项式倍增 fwt dp 区间dp

2020-01-02

0 493

数学专题测试3 题解

A. young 大概的意思是说，由低到高考虑不同的二进制位。形成一个最小生成树，那么最高二进制位不同的情况一定只出现一次。所以除掉最高位之后的情况形成两个集合，递归下去$dp$就好了。一个技巧是，将每个方案的最小值的总和，即$\sum \limits_{i}min(i)$转化为$\s...

莫比乌斯函数组合计数多项式数学杜教筛

2020-01-12

0 414

省选模拟39 题解

A. gift 考虑把需要 $swap$ 的关系表示在图上。于是形成若干个环。容易发现交换的次数就是点数减环数。所以原题转化为环的计数问题。考虑把已有的每个连通块的部分表示出来。容易发现对于一条链我们并不关注中间是谁，只关注链首和链尾的状态，于是可以转化为五种形态。如果已...

lct 二项式反演后缀自动机容斥组合计数

2020-03-06

0 410

省选模拟40 题解

A. 染色问题考虑对每条边 $(a,b)$ 附加两种边权 $(x,y)$ 。对于一种染色方案，当 $col_a=col_b$，边权为 $x$，否则边权为 $y$。取 $x=1,y=0$，一种染色方案的贡献是所有边权的乘积，那么答案就是对于每种染色方案的贡献的和。发现这个玩意可以合并。...

组合计数状压网络流二项式反演

2020-03-08

0 754

组合计数题解乱写

3.组合计数上 1.ARC102E 把当前限制对应的每个二元组提出来。枚举有多少个二元组中的数字出现了，然后问题是每个组中二选一。出现的数字可以出现 $>0$ 次，不在任何一个二元组中的数字可以出现 $\geq 0$ 次。统一一下就可以直接插板法了。 2.小Z的礼物通过...

二项式反演轮廓线容斥组合计数

2020-03-17

0 747