糖果传递 设\(x-i\)表示第\(i\)个人向第\(i-1\)传递的糖果数，\(i\in [1,n],x-i\in \mathjaxbb{z}\) 特别的\(x-1\)表示\(1\)向\(n\)传递的糖果数。 设平均数为\(q\) \(a-i-x-i+x_{i+1}=q\) 则有\(x-i-x_{i+1}=a-i-q\) \(x-1-x-2=a-1-q\) \(x-2-x-3=a-2-q\)

题目链接 题目要求单调不降很不好做。 我们把每个数都加上它的下标，就变成了单调上升序列，值域是\([l+1,r+n]\) 在\([l+1,r+n]\)里面选\(n\)个数和单调上升序列的方案数是一一对应的。 答案是\(\sum_{i=1}^n\binom{r-l+i}{i}=\binom{r-l+n+1}{n}-1\) 因为模数是小质数，用\(lucas\)定理做就可以了。 123456789

题目链接 维护一个栈，表示每个输出字符对应\(tire\)图上的节点，在\(tire\)图上游走时，如果走到某个节点是敏感词结束的地方，就弹出敏感词，并且栈回退到到这个敏感词之前的位置。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include <bits/s

具体证明见wikipedia ## 拉格朗日插值 如果给一个度数为\(n\)的多项式的\(n+1\)个点\((x-i,y-i)\)，那么我们可以用拉格朗日插值将求出这个多项式在所有点的取值。 假设\(x-i\)互不相同，\(F(k)=\sum\limits_{i=0}^{deg} y-i \ell-i(k)\) 其中\(\ell-i\)是拉格朗日基本多项式，\(\ell-i(k)=\prod\

题目链接 这题看起来挺像赛道修建。 但是是要求把所有路选完，所以贪心方法不太一样。 首先，二分以后并不是能选就选，这个看样例就知道。 1234567881 21 31 44 51 66 77 8 \(\text{mid}=2\)时，如果能选就选最后是不合法的，因为有边最后不能放到长度不小于\(2\)的链里面。 考虑最后合并一个点的所有链，如果有多于一条链最后不能合并，那就是不合法的。 所有链都

题目链接 因为是按照\(1-n\)的顺序杀龙，所以每次用的剑是固定的，可以先预处理出来。 每次需要满足 1 .\(atk*x\geq a-i\) 2. \(atk*x\equiv a-i\pmod {p-i}\) 观察数据，可以发现要不\(p-i\)满足\(a-i\leq p-i\)，要不\(p-i=1\) 对于第二种只需要刚好打到不大于\(0\)就可以了。 第一种情况，第一个限制显然是可以忽

题目链接 神仙思路。 每次g种树树把左端点插到一个树状数组\(a\)，右端点插\(b\)。 每次查询查\(qry(r,a)-qry(l-1,b)\) 为什么这样是对的呢？ \(qry(r,a)\)表示所有左端点在查询区间\(l\)右边的，这些树有可能会对答案产生贡献。 但是有些树没有贡献，只有这些区间右端点比\(l\)小的时候。 12345678910111213141516171819#in

题目链接 \(\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)

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^{{\fr

题目链接 我甚至不知道数大小是多少？ 因为要选一半的数，所以每个数被选的概率是\(\frac{1}{2}\) 我们直接随机一个数，它大概率最后会被选。 那么现在只用计算这个数最后被选时，可能的\(\gcd\)是多少。 \(\gcd\)一定是数\(x\) 的一个约数，所以分解\(x\)后求出所有约数。 求出所有\(a-i\)和\(x\)的\(\gcd\)，用桶\(cnt[i]\)记录每个\(\g