牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共33篇）

杂题

1.容易发现题意中的子序列没啥用，其实要求的是集合个数。然后考虑并不是所有的点对都是需要关注的，处理的方法是把所有的数按照大小排序。其实按照大小排序就是 $0/1 tire$ 树的样子，所以这样做的话，一个集合中的两两最小异或值实际上就是按照顺序的两两异或值的最小值。然后只要考虑每个...

dp 期望容斥字符串组合计数

2020-04-07

0 457

省选模拟83 题解

A. table 首先考虑怎么暴力 dp，然后发现难点在于怎么知道不受影响的格点的个数。其实特殊之处在于碰到矩形边界之后没办法计数，所以考虑枚举在哪个位置碰到了矩形边界。然后发现每次转移是类似的，只要求 $a$ 次向下走，$b$ 次向右走，$c$ 次在边界上走能贡献的总的权值。其实等价...

组合计数树状数组 dp

2020-04-29

0 413

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