LOJ 10115 校门外的树
神仙思路。
每次g种树树把左端点插到一个树状数组\(a\)，右端点插\(b\)。
每次查询查\(qry(r,a)-qry(l-1,b)\)
为什么这样是对的呢？
\(qry(r,a)\)表示所有左端点在查询区间\(l\)右边的，这些树有可能会对答案产生贡献。
但是有些树没有贡献，只有这些区间右端点比\(l\)小的时候。
1 |
|
LOJ 6682 梦中的数论
题目链接
\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{k=1}^{n}[(j\mid i) \land ((j+k)\mid i)]\)
\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{d=j+1}^{j+n}[(j\mid i) \land (d\mid i)]\)
把枚举后验证变为直接计算贡献，显然只有当\(j,d\)是\(i\)的约数时才有贡献。
从\(i\)的约数中选两个大小不同的约数的选法有\(\binom{\sigma-0 i}{2}\)种。
即求\(\sum\limits_{i=1}^n\frac{\sigma-0^2
i-\sigma-0 i}{2}\)
因为\(\sigma\)是积性函数，用数论分块和\(\text{min25}\) 分别求解即可。
1 | #include <cstdio> |
min-25筛学习笔记
min-25筛学习笔记 参考 好像有些地方把\(F\)，\(f\)搞混了，应该能看懂吧（
\(\text{min25}\)筛是一种求积性函数前缀和的筛法。 即\(\sum\limits_{i=1}^{n}F(i)\)，要求\(\sum\limits_{i=1}^{n}[i\in prime]*F(i)\)可以被快速算出。 时间复杂度 $\mathjaxcal{O}(\frac{n^{{\frac{3}{4}}}}{\log-2n})$ ，空间复杂度\(\mathjaxcal{O}(\sqrt{n})\)。
min-25筛
预处理
计算\(\sum\limits_{i=1}^{cnt}F(p-i)=\sum\limits_{i=1}^{n}[i\in prime]*F(i)\) 定义\(g(n,j)=\sum\limits_{i=2}^nf(i)*[i\in prime\vee r(i)>p-j]\)，\(r(i)\)表示\(i\)的最小素约数。 这里，\(f\)和\(F\)不一样，\(f\)的每一个数都和\(F\)为素数时的计算方法一样，因为好算\(g\)。 形象理解\(r(i)>p-j\) 表示埃氏筛第\(j\) 次后还没筛出的数\(f(i)\)之和。 因为每个\(i\)都一定有素约数\(\leq\sqrt{i}\)。 最后\(g(n,cnt)\)即为所求。
所以\({p-j}^2>n\)时，\(g(n,j)=g(n,j-1)\)，因为\(p-j\)并没有多筛出的数。 \({p-j}^2\leq n\)时，考虑\(p-j\)的贡献。 多出来的部分无非就是\(r-i=p-j\)的数，这些数显然不大于\(\lfloor\frac{n}{p-j}\rfloor\)，且\(r-i>p_{j-1}\)。 \(g(n,j)=g(n,j-1)-f(p-j)\times (g(\frac{n}{p-j},j-1)-\sum\limits_{k=1}^{j-1}f(p-k))\) 因为\({p-j}^2\leq n\)，所以\(\lfloor\frac{n}{p-j}\rfloor\geq p-j\)。 因为枚举了\(p-1,p-2,\text{...},p_{j-1}\)，这些数乘上\(p-j\)后\(r-i<p-j\)，所以应当把多算的部分减去。
计算
我们现在知道\(\sum\limits_{i=1}^{n}F(i)\)素数部分的贡献。 设一个二元组\(s(n,j)=\sum\limits_{i=2}^nF(i)[r(i)\geq p-j]\)
可以发现\(\sum\limits_{i=1}^{n}F(i)=s(n,1)+F(1)\) 考虑计算\(s(n,j)\) , 运用之前预处理的答案，素数部分的贡献是\(g(n,cnt)-\sum\limits_{i=1}^{j-1}f(p-j)\)。 合数部分我们枚举最小的质因子\(p-k\)和幂次\(e-i\) $s(n,j)=g(n,cnt)-\sum\limits_{i=1}^{j-1}F(p-j)+\sum\limits_{k=j}^{{p-k}^2\leq n}\sum\limits_{e=1}^{p-k^{e+1}\leq n}F(p-k^e)s(\frac{n}{p-k^e},k+1)+F(p-k^{e+1})$ 边界是\(n=1\vee p-j>n\)，\(s(n,j)=0\) 时间复杂度 $\mathjaxcal{O}(\frac{n^{{\frac{3}{4}}}}{\log-2n})$
例题
51nod 3152 取数游戏
我甚至不知道数大小是多少？
因为要选一半的数，所以每个数被选的概率是\(\frac{1}{2}\)
我们直接随机一个数，它大概率最后会被选。
那么现在只用计算这个数最后被选时，可能的\(\gcd\)是多少。
\(\gcd\)一定是数\(x\) 的一个约数，所以分解\(x\)后求出所有约数。
求出所有\(a-i\)和\(x\)的\(\gcd\)，用桶\(cnt[i]\)记录每个\(\gcd\)出现的次数。
要求每一个约数的\(cnt\)，只需要找到所有的\(d\mid d-i\)，\(cnt-d\text{加上}cnt_{d-i}\)。
而不用每一个数都唯一分解暴力找。
因为对于当前要求的\(cnt-d，\)\(a-i\)和\(x\)的\(\gcd\)无非两种情况
1. \(\gcd(a-i,x)=d\)，这种情况已经记录。
2. 另一种是\(g=\gcd(a-i,x)\)不等于\(d\)，如果\(d\mid
g\)，这个\(a-i\)也要记到\(cnt-d\)贡献里面。
注意在算\(cnt\)时的顺序，更新\(cnt_{\gcd}\)以后应该从小的数更新到大的数，不然有可能会算重。因为只能从\(\gcd\)那里更新下来
最后扫一遍\(cnt\)数组，更新所有\(cnt-i\geq\left\lceil\frac{n}{2}\right\rceil\)
假设随机\(k\)次，时间复杂度\(\mathjaxcal{O}(k(n\log a+\sqrt{a}+\sigma(a)^2))\)
1 | #include <bits/stdc++.h> |
LOJ 2038 超能粒子炮・改
题目
求\(\sum\limits_{i=0}^{k}\binom{n}{i}\bmod
2333\)
## 分析
用卢卡斯定理拆组合数。
\(\sum\limits_{i=0}^{k}\binom{n/p}{i/p}\binom{n\bmod
p}{i\bmod p}\bmod 2333\)
观察一下发现等于,
\(\binom{n/p}{0}\sum\limits_{i=0}^{p-1}\binom{n\bmod
p}{i}+\binom{n/p}{1}\sum\limits_{i=0}^{p-1}\binom{n\bmod
p}{i}+\binom{n/p}{2}\sum\limits_{i=0}^{p-1}\binom{n\bmod
p}{i}+\text{...}+\binom{n/p}{k/p}\sum\limits_{i=0}^{k\bmod
p}\binom{n\bmod p}{i}\)
也就是\(\left\{\binom{n/p}{0}+\binom{n/p}{1} +\text{...}+{\binom{n/p}{n/p-1}}\right\}\times \sum\limits_{i=0}^{p-1}\binom{n\bmod p}{i}+\binom{n/p}{k/p}\sum\limits_{i=0}^{k\bmod p}\binom{n\bmod p}{i}\)
我们令\(f(n,k)\)表示\(\sum\limits_{i=0}^{k}\binom{n}{i} \bmod
2333\)
则\(f(n,k)=f(n/p,n/p-1)\times f(n\bmod
p,p-1)+f(n\bmod p,k\bmod p)\times \binom{n/p}{k/p}\)
显然取模的可以暴力预处理，除号用卢卡斯定理。
1 | #include <bits/stdc++.h> |
BZOJ 1034 泡泡堂BNB
田忌赛马 1. 如果最强的能赢最强的，先赢一把 2.
最弱的能赢最弱的，先赢一把
3. 否则用最弱的打最强的
1 | #include <bits/stdc++.h> |
LOJ 6165 一道水题
把每个数唯一分解\(n=\prod
p-i^{e-i}\)，显然最终答案的每个质因数指数都不小于\([1,n]\)的每个数分解的指数。
但是这样是\(\mathjaxcal{O}(n\sqrt{n})\)的。
我们只用关心每个质数最大的\(e-i\)是多少。
显然是其他数都是\(1\)的时候，不断用\(n\)除就能得到\(e-i\)的值。
话说我怎么要用\(bitset\)才能过这道题啊...
1 | #include <bits/stdc++.h> |
P6713 [CCO2018] Geese vs. Hawks
翻译好像没太说清楚啊?QAQ
## 题意
两个人分别在看两支球队比赛, 并且只记录了自己观看一方的胜负和得分.
现在问你,是否能够从两个人的记录中选出一些合法的比赛,使得分之和最大.
合法的意思是赢了的一方得分比对方高.
注意没选的比赛也要合法.(这就是为什么第二个样例没有选\((2,3)\)的原因)
题解
并没有要求打印方案,所以有一个很好想的\(DP\)?
设\(f[i][j]\)表示考虑了第一个人的前\(i\)个记录,第二个人的前\(j\)个记录时的最优答案.
转移的时候先令\(f[i][j]=max(f[i-1][j],f[i][j-1])\).
然后如果\((i,j)\)合法,\(f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]+b[j]\).
其实就是\(LCS\)模型吧.
代码
1 | #include<bits/stdc++.h> |
P4173 残缺的字符串
更精彩内容看这个巨佬的博文
没想到字符串匹配还能这么玩
把比较两个字符串的过程形式化, 判断两个字符串相等\(a[i]-b[i]=0\)
普通的模式串匹配
若模式串与另一个串以\(x\)结尾的字串匹配, 即\(P(x)=\sum\limits_{i=0}^{m-1}(a[i]-b[x-m+i+1])=0\).
但是这样是有问题的,两个字符串只要字符种类和个数相同就被认为匹配了...
原因是会出现负号...
令\(P(x)=\sum\limits_{i=0}^{m-1}(a[i]-b[x-m+i+1])^2\)就解决这个问题了.
大力展开式子并翻转 a 串, 可以发现第三项是卷积形式, 可以用 FFT 优化
那么通配符怎么办? 重新设计\(P(x)\),
我们只需要让通配符的匹配函数都等于\(0\)就可以了.
把 * 对应\(0\), 就是满足\(P(x)=\sum\limits_{i=0}^{m-1}(a[i]-b[x-m+i+1])^2a[i]b[x-m+i+1]=0\).
大力展开式子, \(P(x)=\sum\limits_{i=0}^{m-1}a[i]b[x-m+i+1]^3+a[i]^3b[x-m+i+1]+2a[i]^2b[x-m+i+1]^2\)
翻转一下 a 串, 即\(a[i]=a'[m-i-1]\).
\(P(x)=\sum\limits_{i=0}^{m-1}a'[m-i-1]b[x-m+i+1]^3+a'[m-i-1]^3b[x-m+i+1]+2a'[m-i-1]^2b[x-m+i+1]^2\)
可以发现这三个都是卷积形式, 所以做三次 FFT, 一次
IFFT就可以解决问题了.
时间复杂度\(\mathjaxcal{O}(n\log n)\),
常数有点大, 还有这道题卡精度, 把 eps 设置大一点可过
1 | #include <bits/stdc++.h> |
LOJ 2074 灯塔
题目要求\(p-i\geq
h-j+\sqrt{|i-j|}-h-i\)
即\(p-i=\max\limits_{j=1}^{n}h-j+\left\lceil\sqrt{|i-j|}\right\rceil
-h-i\)
因为可以观察的到\(\left\lceil\sqrt{|i-j|}\right\rceil\)取值个数是\(\mathjaxcal{O}(\sqrt{n})\)的。
所以枚举所有长度根号的上取整值，\(RMQ\)上查询对应区间的最大最小值。
即可\(\mathjaxcal{O}(n\log
n+n\sqrt{n})\)时间内完成。
据说还有\(\mathjaxcal{O}(n\log
n)\)的做法，咱也不会啊...
这题把高度改成小数就没法把小数改成上取整的了，这做法不就被卡了吗
1 | #include <bits/stdc++.h> |