牛客237787563号

未归档

/ 注册

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

bzoj2839 集合计数组合计数容斥原理|题解

集合计数题目描述一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）输入格式 ...

组合计数容斥数学

2019-07-02

0 473

赛艇题解

一颗赛艇 https://www.lydsy.com/JudgeOnline/problem.php?id=4584 虽然名字听起来很暴力（+1s），却是组合计数好题，在考试时都没有看出来是组合计数。对于子任务1/2 区间的总长度不超过1e6，可以将区间内的每个数离散化到一个区间里。...

数学组合计数 dp

2019-07-15

0 437

模拟5 题解

星际旅行题中很特殊的给出，恰好2条边1次经过，m-2条边2次经过，让我有一点想到了欧拉路。然而考试中还是没有想到拆边这个巧妙的方法，只打了一个dfs。正解是将每条边拆为两条，问题转化为删去两条不同的边，使图中存在欧拉路。判断每个点的度即可。在每个边拆为两条之后，每个点的度一定是偶...

dp 组合计数图论欧拉路数论分块数学

2019-07-18

0 378

模拟6 题解

A. 那一天我们许下约定在写出来复杂度为$O(nmd)$的简单dp后，我们考虑优化。题中D的范围远大与N和M，我们在dp的过程中，很多一个饼干都不给的天数是无效的一天。于是我们dp出用i的有效天分完n个饼干的方案数，然后把这i个有效天分配到d天里即可。 $ans= \sum \...

dp 组合计数最短路基环树

2019-07-21

0 331

模拟7 题解

A. 方程的解 a，b均为正整数，exgcd求出x最小和最大的解。作差后除公差再加一，就是方程的解的数量。对于a，b，c中存在0或负数的情况，疯狂加特判。 B. visit 共走t步，要求到达坐标$(n,m)$。即总共向上走了n步，向右走了m步。设u为向上走步数，d为向下...

exgcd 数学组合计数 lucas定理中国剩余定理模拟 set

2019-07-22

0 414

模拟9 题解

A. 随 (rand) 尽量不要重载乘法，真的很慢。 50分算法因为重载乘法被卡常卡成20分，真的很伤。 $void$函数，传入希望存储答案的指针，使用$memcpy$快速传递。 1 void mult(const matrix &a,const matrix &...

组合计数 dp 数学期望矩阵线性代数树上差分原根

2019-07-27

0 338

模拟11 题解

A. string 类似 HEOI2016排序。排序这道题因为只询问单点最终答案，二分答案，将小于和大于等于答案的数分别设为0 1，用线段树维护0 1的排序即可。算法一：本题中的1～n变成了0～25（即a～z），单点询问变成了全体询问。仿照排序那道题的做法，线段树优...

线段树 dp trie树组合计数

2019-08-02

0 442

模拟15 题解

A. 建设城市（city）相较于那一天我们许下约定，数据范围有所改变。如果不考虑k的限制，是显然的插板法。枚举至少超过限制的个数，大力容斥就完了。 B. 轰炸行动（bomb）论如何看懂题。如果能够理解题意，缩了scc，拓扑排序求个点带权最长链就完...

容斥组合计数数学 tarjan 图论 dp 期望

2019-08-10

0 337

模拟32 题解

A. chinese 要求的答案是所有情况总的炼字个数。观察到题中k的范围比较小，所以对k下手。枚举炼字的大小，限制与它同一行同一列的数的大小，其它数随便选就可以了。直接快速幂，$O(klogmod)$可过。写的帅一点，弄个线性筛，直接推一些东西，复杂度就变成$O(\frac{kl...

单调队列期望组合计数

2019-09-03

0 307

模拟37 题解

A. 简单的区间看到这种题，一眼就是枚举最值，则确定左右区间，统计跨最值点的答案。维护前缀和后缀和就完了。于是自然地想到用个主席树，还是枚举小的区间，复杂度$O(nlog^2n)$。复杂度证明见模拟31 C.English 正确的算法一定无法避免枚举小区间，已经带了一个log， ...

启发式合并单调栈 ST表桶分治组合计数 dp

2019-09-06

0 502