Q779’s Blog

洛谷P5110 块速递推 题解 题目链接：P5110 块速递推 题意：给定一个数列 \(a\) 满足递推式 \[ a_0=0,a_1=1 \\a_n = 233a_{n-1}+666a_{n-2} \] 求 \(a_n \bmod (10^9+7)\) 多组询问 这个题是有个循环节的，正好是 \(10^9+6\) ，据出题人说是凑好的 关于循环节怎么求的我也不太清楚，先留个坑，研究好了就补上来 upd.20220721 现在知道怎么求循环节了，详见本文最后 也就是，如果数列 \(a_n\) 在模 \(M\) 意义下存在循环节 \(p\) ，则有 \(a_n \equiv a_{n\,\bmod\, p} \bmod M\) 本题的解法就是手推通项公式 具体方法如下 对于二阶线性递推数列 \[ a_0=A,a_1=B \\a_n = pa_{n-1}+qa_{n-2} ,n\ge 2 \] 考虑使用特征方程求解 \(a_n=pa_{n-1}+qa_{n-2}\) 的特征方程为 \[ x^2=px+q \] 可以求出两个特解（不一定是实数） \(x_1,x_2\) ，则 \[ a...

洛谷P5322 [BJOI2019] 排兵布阵 题解 题意：小 C 正在玩一款排兵布阵的游戏。在游戏中有 \(n\) 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 \(m\) 名士兵，可以向第 \(i\) 座城堡派遣 \(a_i\) 名士兵去争夺这个城堡，使得总士兵数不超过 \(m\)。 如果一名玩家向第 \(i\) 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 \(i\) 分。 现在小 C 即将和其他 \(s\) 名玩家两两对战，这 \(s\) 场对决的派遣士兵方案必须相同。小 C 通过某些途径得知了其他 \(s\) 名玩家即将使用的策略，他想知道他应该使用什么策略来最大化自己的总分。 由于答案可能不唯一，你只需要输出小 C 总分的最大值。 设 \(dp[i][j]\) 表示第 \(i\) 个城堡放 \(j\) 个士兵可以获得的最大分数 显然我们会选择恰好为某名玩家放的兵数 \(x\) 的 \(2x+1\) ，不然多的都是浪费 因此这就是个类似背包的问题 没什么难度，直接看代码就能明白了吧（逃 时间复杂度 \(O(nms)\) ...

洛谷P5365 [SNOI2017] 英雄联盟 题解 题目链接：P5365 [SNOI2017] 英雄联盟 题意：正在上大学的小皮球热爱英雄联盟这款游戏，而且打的很菜，被网友们戏称为「小学生」。 现在，小皮球终于受不了网友们的嘲讽，决定变强了，他变强的方法就是：买皮肤！ 小皮球只会玩 \(\text{N}\) 个英雄，因此，他也只准备给这 \(\text{N}\) 个英雄买皮肤，并且决定，以后只玩有皮肤的英雄。 这 \(\text{N}\) 个英雄中，第 \(\text{i}\) 个英雄有 \(K_i\) 款皮肤，价格是每款 \(C_i\) Q 币（同一个英雄的皮肤价格相同）。 为了让自己看起来高大上一些，小皮球决定给同学们展示一下自己的皮肤，展示的思路是这样的：对于有皮肤的每一个英雄，随便选一个皮肤给同学看。 比如，小皮球共有 5 个英雄，这 5 个英雄分别有 \(\text{0,0,3,2,4}\) 款皮肤，那么，小皮球就有 \(3 \times 2 \times 4 = 24\) 种展示的策略。 现在，小皮球希望自己的展示策略能够至少达到 \(\text{M}\) 种，请...

洛谷P5658 [CSP-S2019] 括号树 题解 题目链接：P5658 [CSP-S2019] 括号树 题意：略。 注意到本题中，链的部分分很高，就先考虑这种情况 不难发现，每个与 \(l\) 配对的右括号 \(r\) 的贡献为 \(dp[r]=dp[l-1]+1 = dp[fa[l]]+1\) 则 \(k_i = dp[i] + \sum dp[j]\) ，\(j\) 是 \(i\) 的祖先结点 显然这个性质可以推广到树上 这样维护一个括号栈就好了，怎么维护呢？ 为了防止栈在回溯过程中被破坏，考虑回溯时执行相反操作 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(5e5+15) int n,fa[N],sum[N]; char val[N]; struct Edge { int u,v,next; }e[N]; int pos=1,head[N],...

洛谷P5656 【模板】二元一次不定方程 (exgcd) 题解 题目链接：P5656 【模板】二元一次不定方程 (exgcd) 题意：给定不定方程 \[ ax+by=c \] 若该方程无整数解，输出 \(-1\)。 若该方程有整数解，且有正整数解，则输出其正整数解的数量，所有正整数解中 \(x\) 的最小值，所有正整数解中 \(y\) 的最小值，所有正整数解中 \(x\) 的最大值，以及所有正整数解中 \(y\) 的最大值。 若方程有整数解，但没有正整数解，你需要输出所有整数解中 \(x\) 的最小正整数值， \(y\) 的最小正整数值。 正整数解即为 \(x, y\) 均为正整数的解，\(\boldsymbol{0}\) 不是正整数。 整数解即为 \(x,y\) 均为整数的解。 \(x\) 的最小正整数值即所有 \(x\) 为正整数的整数解中 \(x\) 的最小值，\(y\) 同理。 \(1\le a,b,c\le 10^9\) 根据裴蜀定理， 对于 \(x,y\) 的二元一次不定方程 \(ax+by=c\) ，其有解的充要条件为 \(\gcd(a,b) \mid c\) ...

洛谷P5851 [USACO19DEC]Greedy Pie Eaters P 题解 题目链接：P5851 [USACO19DEC]Greedy Pie Eaters P 题意： Farmer John 有 \(M\) 头奶牛，为了方便，编号为 \(1,\dots,M\)。这些奶牛平时都吃青草，但是喜欢偶尔换换口味。Farmer John 一天烤了 \(N\) 个派请奶牛吃，这 \(N\) 个派编号为 \(1,\dots,N\)。第 \(i\) 头奶牛喜欢吃编号在 \(\left[ l_i,r_i \right]\) 中的派（包括两端），并且没有两头奶牛喜欢吃相同范围的派。第 \(i\) 头奶牛有一个体重 \(w_i\)，这是一个在 \(\left[ 1,10^6 \right]\) 中的正整数。 Farmer John 可以选择一个奶牛序列 \(c_1,c_2,\dots,c_K\)，并让这些奶牛按这个顺序轮流吃派。不幸的是，这些奶牛不知道分享！当奶牛 吃派时，她会把她喜欢吃的派都吃掉——也就是说，她会吃掉编号在 \([l_{c_i},r_{c_i}]\) 中所有剩余的派。F...

洛谷P6216 回文匹配 题解 题目链接：P6216 回文匹配 题意：对于一对字符串 \((s_1,s_2)\)，若 \(s_1\) 的长度为奇数的子串 \((l,r)\) 满足 \((l,r)\) 是回文的，那么 \(s_1\) 的“分数”会增加 \(s_2\) 在 \((l,r)\) 中出现的次数。 现在给出一对 \((s_1,s_2)\)，请计算出 \(s_1\) 的“分数”。 答案对 \(2 ^ {32}\) 取模。 容易发现这就是个Manacher+KMP Manacher用于找出奇回文串，KMP用于找出 \(s_2\) 在 \((l,r)\) 中的出现位置 难点在于如何计算这个次数 对于每个极大回文串（长度小于 \(|s_2|\) 的不考虑） 它一定包含了在同一回文中心的更小的回文串 如abbba还包含了bbb,b 如果暴力去求解，时间复杂度为 \(O(n^2)\) 于是想到前缀和来加快运算 我们可以在匹配成功时将 \(s_2\) 左端点位置标记为 \(1\) 考虑一个回文串，x为任意字符 str:xxxxxxx pos:1234567 它对答案的贡献为sum_6...

洛谷P6327 区间加区间sin和 题解 题目链接：洛谷P6327 区间加区间sin和 题解 题意：维护一个数据结构，支持 区间加 \(v\) 询问区间 \(\sum\limits_{i=1}^{r}\sin a_i\) 注意到 \[ \begin{aligned} \sin(a+x)&=\sin a\cos x+\cos a \sin x\\ \cos(a+x)&=\cos a\cos x-\sin a \sin x \end{aligned} \] 直接维护即可两个量即可 注意点： 更新的时候拿之前更新过的sin去更新cos，爆零。 不开long long，爆零。 不下传标记，爆零。 可以适当卡卡常（逃 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(2e5+15) #define ls(at) (at<<1) #define rs(at) ...

等差数列&等比数列小结 高一自学的时候瞎总结写的（好吧我现在还是高一 2022.5.7） 感觉丢在文件夹里吃灰没啥用，就放上来了 一、等差数列 等差数列通项公式 \[ a_n = a_1+(n-1)d \] \(S_n\) 表示等差数列 \(\{a_n\}\) 的 前 \(n\) 项和 \[ \begin{aligned} S_n &= \sum\limits_{i=1}^{n}a_n\\&=na_1+\dfrac{n(n-1)}{2}d\\&=\dfrac{d}{2}n^2+\left(a_1-\dfrac{d}{2}\right)n \end{aligned} \] 易知 \[ \begin{aligned} S_n&=\dfrac{n(a_1+a_n)}{2}\\&=\dfrac{n(a_m+a_{n-m+1})}{2} \end{aligned} \] \[ S_{2n-1}=(2n-1)a_n \\S_{2n}=n(a_n+a_{n+1}) \] \(\{a_n\}\) 为等差数列当且仅当 \[ S_n=An^2+Bn+...

线段树空间开4倍的原因 如果证明有错欢迎指出。 对于长为 \(n\) 的序列，显然以其构建的线段树有 \(n\) 个叶子节点 此时线段树的高度为 \(k=\left\lceil{\log_2 n}\right\rceil+1\) （第一层的高度为 \(1\) ） 通过等比数列求和公式 \[ \begin{aligned} S_n= \begin{cases} na_1,&q=1 \\\\ \dfrac{a_1\left(1-q^n\right)}{1-q} = \dfrac{a_1-a_nq}{1-q} ,&q\ne 1 \end{cases} \end{aligned} \] 可知 至多有 \(\dfrac{1\times(1-2^k)}{1-2} = 2^k-1\) 个结点 即有 \(2^{\left\lceil{\log_2 n}\right\rceil+1}-1\) 个结点 根据 \[ \begin{aligned} &\left\lceil{x}\right\rceil- \left\lfloor{x}\right\rfloor=\begin{c...

主定理 证明先不写 将一个规模为 \(n\) 的问题，通过分治得到 \(a\) 个规模为 \(n/b\) 的子问题，每个递归带来的额外计算为 \(f(n)\) ，则有 \[ T(n)=aT(n/b)+f(n) \] 其中 \(a,b\) 为常数， \(n\in \mathbb{N}^*,a\ge 1,b > 1,n/b\) 解释为 \(\left\lfloor{\dfrac{n}{b}}\right\rfloor\) 或 \(\left\lceil\dfrac{n}{b}\right\rceil\) 若 \(\exists \epsilon > 0\) 使得 \(f(n)=O(n^{\log_b{a}-\epsilon})\)，则 \(T(n)=\Theta(n^{\log_ba})\) 若 \(\exists \epsilon \ge 0\) 使得 \(f(n)=\Theta(n^{\log_ba}\log^\epsilon n)\)，则 \(T(n)=\Theta(n^{\log_ba}\log^{\epsilon+1}n)\) 若 \(\exists \eps...

杂题选做[2] 今天加大了难度 \(🤤\) ，但是q779太菜了 一些q779感觉较难的题会单独写题解（逃 一些收获： 求最小环要先给图赋值 INF ，而且 INF 不能开 0x3f3f3f3f3f3f3f3f ，会爆 long long 的 long long的话用 0x1f1f1f1f1f1f1f1f 差不多（逃 然后别忘了判重边 匈牙利叫Hungary（逃 P2738 [USACO4.1]篱笆回路Fence Loops 最小环，建图麻烦，要去个重 题解：link 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x1f1f1f1f1f1f1f1f namespace FastIO { #define gc() readchar() #define pc(a) putchar(a) #define SIZ (int)(1e6+15) char buf1[SIZ],*p1,*p2; char r...