Q779’s Blog

浅谈拉格朗日插值法 模板题链接：P4781 【模板】拉格朗日插值 题意： 给定 \(n\) 个点 \(P_i(x_i,y_i)\) ，将过该 \(n\) 个点的最多 \(n-1\) 次多项式记为 \(f(x)\) 给出 \(k\) ，求 \(f(k) \bmod 998244353\) \[ f(k) = \sum\limits_{i=1}^{n}y_i\prod_{j\ne i}{ \dfrac{k-x_j}{x_i-x_j} } \] 证明：过 \(P_i\) 作垂线交 \(x\) 轴于 \(H_i(x_i,0)\) 构造 \(g_i(x),i=1,2,\cdots ,n\) ，使得 \(g_i(x)\) 的图像过 \(\begin{cases}P_i(x_i,y_i) \\[8pt] H_j(x_j,0),j\ne i\end{cases}\) 可以发现，\(g_i(x) = a \prod_{j\ne i}{(x-x_j)}\) ，其中 \(a\) 是未知数 因为 \(g_i(x)\) 过 \(P_i(x_i,y_i)\) ，代入并整理可得 \[ a = \dfrac...

洛谷P2633 Count on a tree 题解 题目链接：P2633 Count on a tree 题意：给定一棵树和 \(u,v,k\) ，求 \(u,v\) 结点间的第 \(k\) 小点权 本来以为是个树链剖分+主席树，结果发现并不可做 观察到主席树本质上利用了前缀和来计算线性的区间和 现在就是把求和搬到了树上 可以立即想到树上差分 不过这道题不是树上差分，可能应该叫树上前缀和更恰当一些 对于一条根结点（无根树就假定是 \(1\) 好了）到叶子结点的简单路径，就是一个线性区间上的主席树 也就是在树上建立了类似前缀和体系的主席树群，每一个主席树维护了一条根结点到叶子结点的路径上的结点的信息 感性理解一下，有点“前缀主席树”的感觉 那么 \(u\) 到 \(v\) 的信息就是 sum[u]+sum[v]-sum[lca(u,v)]-sum[fa[lca(u,v)][0]] 是不是很像树上差分了 其他的比如离散化什么的都是基本操作了，这里不再赘述了 qwq 时间复杂度 \(O(n\log n)\) 代码如下 #include <bits/stdc++.h> usi...

ubuntu和windows chrome浏览器 关闭what‘s new页面 在搜索栏里输入chrome://flags 修改操作如下

windows Matlab R2020b 安装教程 前言 本文其实是我自己在安装过程中截图的，现在搞定了整理出来给大家参考一下 使用的是matlab R2020b 如果本文有什么错误或对本文有什么问题，欢迎留言 qwq 要是图挂了可以直接私信我，只要我还在 一、下载文件 下载好文件，我就放张图 要尽量支持正版哦，这是正版软件下载链接 https://ww2.mathworks.cn/products/matlab.html 在这里插入图片描述 二、解压文件 选中上面的那些.rar文件，然后解压（我建议用360压缩，挺好用的，不是打广告qwq） 在这里插入图片描述 然后稍微整理一下，留下有用的，如下 注：第二个文件夹就是解压后的东西，我不放心就先留着了 在这里插入图片描述 三、开始安装 打开.iso的文件，然后双击setup文件 四、安装细节 在这里插入图片描述 安装密钥是 09806-07443-53955-64350-21751-41297 在这里插入图片描述 许可证就选择刚刚下载的文件夹里...\crack\license_stan...

windows 设置需要管理员权限时输入密码才能操作 步骤如下 首先 win+r，输入regedit打开注册表编辑器 然后找到 计算机\HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\System\ConsentPromptBehaviorAdmin 将值修改为 3 （十六进制） 不明白的话可以看看下面的图 然后尝试打开一下任务管理器 就发现需要PIN啦！

ubuntu GIMP 字体显示异常 解决方法 今天用GIMP的时候发现字体出了问题 报错如下 Fontconfig warning: FcPattern object width does not accept value [75 100) /snap/gimp/380/usr/bin/gimp: Gimp-Text-严重: gimp_font_factory_load_names: assertion 'fontset' failed (gimp:25382): GdkPixbuf-CRITICAL **: 12:21:22.032: gdk_pixbuf_scale_simple: assertion 'dest_width > 0' failed (gimp:25382): GdkPixbuf-CRITICAL **: 12:21:22.032: gdk_pixbuf_get_width: assertion 'GDK_IS_PIXBUF (pixbuf)'...

ubuntu WPS字体缺失 解决方法 前言 请保证您还有一台windows 一、在windows复制字体 首先在windows下载好WPS，然后找到字体，复制 在这里插入图片描述 二、复制到ubuntu 我的ubuntu上装了WPS2019，目录在/usr/share/fonts/wps-office 因此只要在终端输入 sudo cp ./* /usr/share/fonts/wps-office 就好了 三、重启WPS 关掉再打开 总结 从windows上复制到ubuntu

洛谷P1486 [NOI2004] 郁闷的出纳员 题解 题目链接：P1486 [NOI2004] 郁闷的出纳员 题意：维护一个数据结构，支持 插入一个大小为 \(k\) 的值，小于下界时不插入 所有元素加上 \(k\) 所有元素减去 \(k\) ，小于下界的删除 查询所有元素中的 \(k\) 大值 最后输出删除的元素个数（两元素相等算两个） 可以用平衡树来解决本题 听说正解是splay，不过我来讲一种替罪羊树的写法 我们可以维护一个 \(d\) ，表示每次加减的变化 这样每个元素就可以用 \(x+d\) 的形式表示了 在平衡树里放原来的数减去插入时的 \(d\) ，即 \(k-d\) 这样输出的时候就是正常的数了 那小于下界的怎么搞呢？ 根据替罪羊树的性质，我们可以直接把整课树重构 在Flatten操作时判断当前元素 \(x\) 加上 \(d\) 是否超过下界，且存在，否则就直接不管它了 \(k\) 大值直接查 \(num1-k+1\) 小值就好了 这个 \(num1\) 表示每次操作后的剩余结点数（两元素相等算两个） 因为它最后还有个询问删除的，再记录一下总插入结点数（...

ubuntu 卸载fcitx输入法 我又来水文章了 打开终端 输入 sudo apt-get remove fcitx sudo apt-get remove fcitx-module* sudo apt-get remove fcitx-frontend* sudo apt-get purge fcitx* 如果您原来使用的就是fcitx输入法，那再输入一句 sudo reboot 重启以后默认就是ibus输入法啦！ ibus大法好！

均值不等式及其证明 引理1 若 \(a\ge 0,b\ge 0\) ，则 \[ (a+b)^n\ge a^n+na^{n-1}b\qquad (n\in \mathbb{Z}^+) \] 证明直接二项式展开即可。 定理1 \[ \dfrac{\sum_{i=1}^{n}a_i}{n}\ge \left(\prod_{i=1}^na_i\right)^{\frac{1}{n}} \] 证明 考虑数学归纳法。 原命题等价于 \[ \left(\dfrac{\sum_{i=1}^{n}a_i}{n}\right)^n \ge \prod\limits_{i=1}^{n}a_i \] 设 \(n=k\) 时原不等式成立，规定 \(\forall i<j,a_i<a_j\) ，并记 \(S_n = \sum_{i=1}^{n}a_i\) 。 当 \(n=k+1\) 时，原不等式为 \[ \begin{aligned} \left(\dfrac{S_k+a_{k+1}}{k+1}\right)^{k+1} &\ge \prod\limits_{i=1}^{k+1}a...

浅谈分块 区间众数 前言 分块大法好（ 本文直接讲例题了 qwq P4168 [Violet]蒲公英 题目链接：P4168 [Violet]蒲公英 题意: 找到区间内编号最小的众数，强制在线 解法一 直接分块 设块长为 \(len\) ，块的总数为 \(t\) 个 我们先预处理出所有以块的端点为端点的区间众数和众数的出现次数 或者说就是把每个连续块组成的区间都算出编号最小众数和它的出现次数 别忘了离散化，不然MLE咯 总共有 \(t^2\) 个这样的区间，每次处理 \(O(n)\) ，则预处理时间复杂度为 \(O(nt^2)\) 暴力查询时可以在预处理过的数组基础上临时更新数组，以统计答案，再复原数组 总时间复杂度 \(O(nt^2+mn/t)\) 假设 \(m\) 和 \(n\) 数量级相同，解 \(nt^2=mn/t\)，\(t \approx \sqrt[3]{n}\) 则时间复杂度可以控制在 \(O(n^{5/3})\) 内 空间复杂度比较大，\(O(nt^2)\) （注：预处理所需） 代码如下 #include <bits/stdc++.h> using n...

LOJ10050 The XOR Largest Pair 题目链接：LOJ10050 The XOR Largest Pair 题意：给定 \(n\) 个非负整数，任取两个数，使得这两个数的异或结果最大，求这个最大值 肯定不是朴素枚举啊qwq 直接用Trie存每个数的二进制就可以了（注：把二进制看作字符串） 根据异或的定义，对于每个 \(a_j\) ，我们从最高位开始，尽可能取与 \(a_i\) 这一位相反的那一条路，一定可以得到最大值 至于最高位，我们只要不够的补 \(0\) 即可 因为它题目中说了每个数最大不大于 \(2^{31}-1\) ，那么我们直接保存为30位二进制即可 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define MAXN (int)(1e5+5) #define INF 0x3f3f3f3f3f3f3f3f template<typename T>inline void read(T &k) { char ch=g...