ThinkofBlank

分类

未归档(4) 论文(10) 题单(1) 题解(90)

/ 注册

TA的专栏 8篇文章 0人订阅

ThinkofBlank’s

8篇文章 1209人学习

全部文章（共18篇）

NC14731 逆序对题解

这是一道很明显的排列组合题先看题，他叫我们求所有长度为n的01串的逆序对数之和那么，我们可以考虑计算每个位置与它之前的位置所产生的贡献：第1个位置一定不会与之前的位置产生贡献，所以可以不管对于第x(x!=1)个位置，它要和它前面的位置产生贡献的话，那么这个位置上的数就一定得是0，而它前面的就...

数论优化题解

2020-04-15

1 620

牛客算法周周练2 E水题(water) 题解

最让我痛苦的一道题，查错n久，结果发现数组开小了（？？？）这道题其实相当于三道题的杂糅版我们先来考虑第一道（选支）：判断是否存在k使得注意到，x<=1e18 而根据f的递推式，f的上升很快，所以，对于f，我们可以直接暴力计算：当然，我查错的时候，怀疑我计算有锅，于是打表发现，这玩意...

数论题解

2020-04-15

6 786

牛客算法周周练2 C完全平方数题解

比A还签到的签到题。。。求l-r的完全平方数的个数我们按套路将询问拆成两个询问: 求0-r的完全平方数的个数和0-l-1的完全平方数的个数那么，我们需要解的就是求0-x的完全平方数的个数注意到,l可能为0，所以，可能有个询问是求0-(-1)的完全平方数的个数，这个时候特判即可那么，我们来看...

数论题解

2020-04-15

0 735

二分图染色（弱化版）题解

乍看一下，此题貌似很简单，仔细一想，竟然完全不可做。。。然后，开始思考怎么搞这道题。。。首先，我们因为每个边都要染色，所以，我们不妨先给所有边都染上最没影响的颜色——绿色然后，我们只需考虑，将绿色的边改成红色或者蓝色即可~ 我们来推导一下如果既有蓝色，又有红色，尝试推导一下，发现情况太多，而...

数论

2020-04-10

3 906

【数论】整数分块及详细证明

update:添加了数学公式markdown 洛谷博客地址：https://www.luogu.com.cn/blog/KingofNight/post-shuo-lun-zheng-shuo-fen-kuai-ji-yang-xi-zheng-ming 一.复杂度证明引理一:对于任意一个正...

数论理解

2018-12-27

0 696

题解 P4980 【【模板】Polya定理】

【模板】Polya定理题解提供一个新算法。。。首先,我们来分析一下题目: 给一个有n个点的环图n种颜色，问本质不同的方案数那么，很明显的，这是一个polya定理（废话，题目名说明了一切）我们先来看看这道题的“操作”，很明显的操作就是只有一个——平移（有人说旋转，但我个人更喜欢看成平移。。。...

数论优化研究

2019-09-23

1 625

快速模拟暴力组合数来自专栏

本题解讲的是快速暴力组合数的方法，需要知道以下知识(能做此题的大佬应该都知道吧。。。)：欧拉筛，组合数公式,卡速米(这个应该没人会吧？) 否则将引起不适设π(x->y)为从x连乘到y(数学公式编译器崩了。。。) 组合数，大家都知道，公式为C(n,m)=!n/(!m*!(n...

数论研究

2018-12-19

0 623

关于扩展欧几里得中求最小非负x的方法的推导

推导假设,我们已经求出有一对x,y满足ax+by=gcd(a,b)。我们想要求最小非负整的x,那么必须要减去一个能减的最大值,我们设减去一个D,则方程变为: a(x-D)+by+aD=gcd(a,b) 整合一下： a(x-D)+b(y-aD/b)=gcd(a,b) 我们...

数论理解

2018-12-19

0 0