牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共3篇）

数学专题测试1 题解

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

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

2020-01-02

0 493

省选模拟30 题解

A. 任凭风浪起，稳坐钓鱼台其实就是一个优化过的暴力。首先答案 $x^3$ 显然可以转化为 $3$ 个位同时出现的方案数*权值求和。当 $k<=20$ ，直接异或 fwt ，然后做一个超集求和运算，$C(k,3)$ 枚举就行了。这个算法不优秀的原因是只关注三个位同时出现，并不需...

数学构造题分治 fwt

2020-02-26

0 498

省选模拟101 题解

石子游戏问题可以简单转化为最少能取出多少个数，使得异或和为 \(k\)。显然答案是小于 \(log(A_i)\) 的，因为线性基已经可以拼出所有数了。所以可以考虑枚举这个答案，然后就是 \(dp_{i,j}\) 表示用 \(i\) 个数能否拼出 \(j\)。转移可以用 \(FWT\) 优化，...

状压容斥 fwt dp 筛法

2020-05-20

0 367