牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共29篇）

模拟21 题解

A. 折纸考虑$O(nm)$暴力，对于每次操作，暴力修改n个点的下标，同时维护左右端点下标，最后相减就是答案。对于后40分，n的范围很大。恰好我们并不关注每个点的下标。对于每次翻折， $O(m)$查询并记录下翻折操作时的下标即可。注意每次操作不能单纯向一个方向翻折。 ...

数学 exgcd 模拟数位dp

2019-08-14

0 410

模拟33 题解

A. 春思比较简单的一道题，甚至是见过的原题。约数和是积性函数，搞一搞等差数列求和，乘到一起就可以了。 B. 密州盛宴显然，方案合法的条件是苏轼每轮都能吃到菜。所以就发现任意后缀0,1个数必须满足，$sufcnt_0-sufcnt_1<=1$。所以当不满...

dp 数学结论题单调指针

2019-09-03

0 348

模拟61 题解

A. 砖块简单模拟。对于最后一问，算一算复杂度就可以知道开map没有任何问题，然而map真的方便很多，所以为什么不用呢。 B. 数字容易发现末尾的0一定是被质因子2和5凑出。并且，对于任意的$n!$，质因子2的个数不小于质因子5的个数。简单的暴力$O(n)$做...

线段树模拟吉司机线段树 Hash 中国剩余定理数学

2019-10-06

0 416

模拟65 题解

A. Simple 首先求出n,m的gcd，那么显然只有gcd的倍数可能被拼出，其他数一定是不好的数。所以问题转化为用$\frac{n}{gcd}$,$\frac{m}{gcd}$，拼不出的$\frac{q}{gcd}$范围内的数。因为除gcd后的n，m互质，用某凯的疑惑中的结论可知最...

贪心直径数学

2019-10-09

0 750

模拟67 题解

A. 神炎皇尝试枚举$a$,$b$的$gcd$，设为$d$。那么有$$ans=\sum \limits_{d=1}^{n} \sum \limits_{i=1}^{n} \sum \limits_{j=1}^{n} [gcd(i,j)==d][i+j<=n][i+j|i=j]$$ ...

dp 数学树状数组

2019-10-10

0 385

模拟70 题解

A. 木板相似三角形，简单推出结论。发现要求的是$\sum \limits_{i=1}^{n-1}[n|i*i]$。那么只要把$n$质因数分解，设为$\prod_{j}^{} p_j^{c_j}$，那么设$k$为最小的合法的$i$，有$k=\prod_{j}^{} p_j^{\l...

数学 dp 构造题搜索

2019-10-13

0 301

关于斯特林数

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

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

2019-12-11

0 428

数学专题测试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

省选模拟30 题解

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

数学构造题分治 fwt

2020-02-26

0 498