搜索结果
查询Tags标签： rfloor，共有 23条记录-
[数学记录]CF896D Nephren Runs a Cinema
题意：给定 \(n=x+y+z\)，求满足以下要求的长度为 \(n\) 的序列的数目：序列由 \(x\) 个 \(1\)，\(y\) 个 \(-1\)，\(z\) 个 \(0\) 组成，序列任意前缀和非负，和在 \([l,r]\) 之间。 考虑确定 \(z\) 和序列和的方案数。 看做卡特兰数类似折线图考虑。则在不能过线的前提下…
2022/9/2 23:53:01 人评论 次浏览 -
P8443 题解
前言 题目传送门！ 更好的阅读体验？ 普及组月赛第一题。别的题解语言有点高深，我补篇题解。 思路 显然，\(\lfloor \dfrac{l}{x}\rfloor, \lfloor \dfrac{l+1}{x}\rfloor, \cdots, \lfloor \dfrac{r}{x}\rfloor\) 是连续的整数。 而且，显然有 \(\operatorname{gcd}(c, …
2022/8/26 6:23:36 人评论 次浏览 -
万能欧几里得算法学习笔记
万能欧几里得算法 基本描述 对于一条直线 \(\dfrac {px+r}{q}\)，满足 \(p>0,q>0,r\in[0,q-1]\)，求解有关 \(\lfloor\dfrac {px+r}{q}\rfloor,x\) 的一些函数。 考虑在坐标系上考虑这条直线，从 \((0,0)\) 开始走。 定义当直线穿过一条形如 \(y=h(h\in\Z)\) 的横线…
2022/8/6 1:23:52 人评论 次浏览 -
【模板】扩展欧几里得算法
【模板】扩展欧几里得算法 void exgcd(int a, int b, int &g, int &x, int &y) {if (!b) x = 1, y = 0, g = a;else {exgcd(b, a % b, g, x, y);int t = x;x = y;y = t - a / b * y;} }如何理解 虽然不知道在推什么但是确实推出来了（？ \[\begin{aligned} \b…
2022/7/26 14:24:59 人评论 次浏览 -
SDSC2021 Day1
又是一年SDSC到但是我已经成为时代的眼泪啦 但我翻翻去年的笔记，好像就Day1写得还行，剩下几天就很摸 所以就只把Day1的笔记搬过来啦~（我才不会说临时起意搬笔记的原因是又有好题图了（当然不是））配套题单 质数筛 提供一种快速的分解质因数的方法： 在线性筛的时候可以…
2022/7/9 23:54:11 人评论 次浏览 -
AcWing 199. 余数之和
题目传送门 零、参考资料 总结与思考：数论分块 【数学】数论分块（整除分块） 一、数论分块的相关概念 “数论分块”这个名词，其实比较模糊，没有一个广泛认同的严格定义。这里讲一下我个人的理解： 令\(\displaystyle f(i)=\lfloor \frac{n}{i} \rfloor\) \(f(i)\)的值…
2022/6/18 23:20:56 人评论 次浏览 -
整除分块 学习笔记
板子题 板子题-UVA11526 题目大意： 给定一个 \(n\)，求 \(\sum\limits_{i-1}^{n}\lfloor \frac{n}{i} \rfloor\)。其中 \(n\) 为 \(32\) 位无符号整数。 题目解析 显然如果暴力求解肯定是不可行的，显然会 TLE，所以我们需要找一种复杂度更优的算法。 我们可以先令 \(n=1…
2022/4/25 23:15:57 人评论 次浏览 -
北大集训 / CTT 2021 部分题解
忘报名北大集训，还是能看到题，省了 8000 块钱，赢麻了。 鸽表示没代码，may be 无正解思路。 Day 1 A. 末日魔法少女计划 鸽。 \(k = 2\) 的做法：考虑分治，取中间点，处理所有跨过中点的，连上左右两边所有到这里的边，递归下去，是 \(O(n \log n)\) ，但是有很多重复…
2022/3/25 6:22:45 人评论 次浏览 -
类欧几里得算法
类欧几里得算法 问题引入 设 \[f(a, b, c, n) = \sum_{i=0}^n \left\lfloor\frac{ai + b}{c}\right\rfloor \]其中 \(a, b, c, n\) 是常数，需要 \(\mathcal O(\log n)\) 的做法。 若 \(a \geq c\) 或 \(b \geq c\)，我们可以将 \(a, b\) 对 \(c\) 取模以简化问题。 考虑到…
2022/3/9 14:14:42 人评论 次浏览 -
【CF1601F】Two Sorts（Meet in Middle）
题目链接定义 \(a_{1\sim n}\) 为将 \(1\sim n\) 按字典序从小到大排序后的结果，求 \((\sum_{i=1}^n(i-a_i)\ \operatorname{mod}\ 998244353)\ \operatorname{mod}\ 10^9+7\)。 \(1\le n\le10^{12}\)题意转化 这题的求和中有两种不同的取模，看起来非常麻烦。 考虑取模的…
2022/3/8 23:19:25 人评论 次浏览 -
Darkbzoj 2818 Gcd
Darkbzoj 2818 Gcd 链接：https://darkbzoj.tk/problem/2818规定 \([x]\) 为逻辑判断函数，若 \(x\) 为真则 \([x]=1\)，否则 \([x]=0\) 。 这题要我们统计的是： \[\sum_{i=1}^{m}\sum_{j=1}^{\lfloor\frac{n}{p_i} \rfloor}\sum_{k=1}^{\lfloor\frac{n}{p_i}\rfloor}[gc…
2022/1/1 23:11:55 人评论 次浏览 -
Darkbzoj 2818 Gcd
Darkbzoj 2818 Gcd 链接：https://darkbzoj.tk/problem/2818规定 \([x]\) 为逻辑判断函数，若 \(x\) 为真则 \([x]=1\)，否则 \([x]=0\) 。 这题要我们统计的是： \[\sum_{i=1}^{m}\sum_{j=1}^{\lfloor\frac{n}{p_i} \rfloor}\sum_{k=1}^{\lfloor\frac{n}{p_i}\rfloor}[gc…
2022/1/1 23:11:55 人评论 次浏览 -
杜教筛
杜教筛作用：用来求积性函数前缀和，时间复杂度为\(O(n^\frac{2}{3})\)积性函数 若对于函数 \(f(x)\) 满足 \(f(x)=f(a)*f(b)\) ，其中 \(x=a*b\) 且 \(gcd(a,b)=1\)，那么 \(f(x)\) 为积性函数。 常见积性函数：\(\mu()\) ——莫比乌斯函数。 \(\phi()\) ——欧拉函数。\…
2021/10/6 23:13:28 人评论 次浏览 -
杜教筛
杜教筛作用：用来求积性函数前缀和，时间复杂度为\(O(n^\frac{2}{3})\)积性函数 若对于函数 \(f(x)\) 满足 \(f(x)=f(a)*f(b)\) ，其中 \(x=a*b\) 且 \(gcd(a,b)=1\)，那么 \(f(x)\) 为积性函数。 常见积性函数：\(\mu()\) ——莫比乌斯函数。 \(\phi()\) ——欧拉函数。\…
2021/10/6 23:13:28 人评论 次浏览 -
[loj138]类欧几里得算法
模板题 定义$\lfloor x\rfloor$表示小于等于$x$的最大整数，$\lceil x\rceil$表示大于等于$x$的最小整数 不难发现，若$a\in Z^{+}$且$b,x\in Z$，则$ax\le b\iff x\le \lfloor\frac{b}{a}\rfloor$、$ax\ge b\iff x\ge \lfloor\frac{b-1}{a}\rfloor+1$ 通过拉格朗日插值法…
2021/9/15 22:05:21 人评论 次浏览
