前置技能：单位根 我们有一个玄学函数f(x)=∑i=0n−1aixif(x)=\sum _{i=0}^{n-1} a_i x^if(x)=∑i=0n−1​ai​xi 不妨换一个好看的形式：f(x)=a0,a1,a2,...an−1f(x)= \\{a_0,a_1,a_2,...a_{n-1} \\}f(x)=a0​,a1​,a2​,...an−1​ 还有另一个玄学函数g(x)=b0,b1,b...

这两个”根“在多项式乘法里面运用非常广泛。 单位根（FFT） 关于我自己对单位根的理解。 单位根其实就是一些复数，他们的模长为111。 所以单位根一定在单位圆上 假设一个单位根zzz的极角为θ\thetaθ，那么我们可以将zzz表示为cos⁡θ+isin⁡θ\cos \theta +i \sin \thetacosθ+isinθ 数形结合考虑，从圆上某一个点做一条垂线，那么垂线长度为sin...

传送门 加不了了，因为CF挂了。 ProProPro 给你nnn，n≤109n \le 10^9n≤109，要你输出一个字符串sss，使得sss有nnn个子串为133713371337，且∣s∣≤105|s|\le 10^5∣s∣≤105 SolSolSol 1.1337......71337......71337......7，nnn个777？但是题目说∣s∣≤105|s| \le 1...

传送门 首先，看到区间修改，区间查询就要想到线段树。 把链上面的操作转化到点上面的的操作，我们像这样编号，点编号为1...n1...n1...n，边编号为1...n−11...n-11...n−1 于是修改和查询都对应到了边[l,r−1][l,r-1][l,r−1] 考虑如何算期望值，下面的分母很简单，就是Cr−l+12C_{r-l+1}^2Cr−l+12​，从r−l+1r-l+1r−l...

传送门 首先，附送本题数据生成器： 1234567891011121314151617181920#include <bits/stdc++.h>using namespace std;inline int gen(){ return (rand()<<15)|(rand());}int main(){ srand(time(...

传送门 一道比较有意思的数学题。 首先，根据贪心的原理，最好把nnn全部分成质数。 考虑分类讨论， 1.n==1n==1n==1或n==2n==2n==2，显然答案是111 2.n>2n>2n>2且nnn为偶数，也就是n≥4n \geq 4n≥4，由哥德巴赫猜想，发现nnn可以分成两个质数之和，所以答案为222 3.n>2n>2n>2且nnn为奇数， 还是...

传送门 首先，大家都可以看出来，这道题是一个多重背包，设f(i)f(i)f(i)为和为iii可不可行，那么假设kkk为{an}\{a_n\}{an​}中的一个数，且f(s)==1f(s)==1f(s)==1，我们把f(s+k×1)f(s+k \times 1)f(s+k×1)，f(s+k×2)f(s+k \times 2)f(s+k×2)，f(s+k×3)f(s+k \times 3)f(s...

传送门 首先，将组成山的线段延长，形成许多直线，发现要使得这座山的任何一个部位都能够被看到，灯必须在所有直线之上，假设灯的坐标为(x,y)(x,y)(x,y)，这可以转化为所有直线上横坐标与之相同的一点(x,y0)(x,y_0)(x,y0​)，有y0≤yy_0 \le yy0​≤y，根据贪心的原则，我们根据xxx算出所有y0y_0y0​后，取一个最大值就可以得出yyy。 设根据xxx算出的纵...

考虑把门iii和门iii中的钥匙指向的门jjj连一条有向边。 打开一扇门，那么这个门处在的环内的所有门都可以被打开，所以图中不可能超过kkk个环。 总共的排列数为n!n!n!，题目所求的是n!n!n!个排列中组成≤k\le k≤k个环的数量，即第一类斯特林数。 考虑到111号门不能炸，用总数Su(n,i)S_u(n,i)Su​(n,i)减去111号点单独成环的方案Su(n−1,i−1)S_u...

传送门 大概就是运用判断中位数的套路吧。 把大于bbb的数设为111，等于的设为000，小于的设为−1-1−1。 若一个数列经过这样处理后和为000，说明ddd为该数列的中位数。 从中位数的位置分别向左向右求前缀和，放进一个桶里面。 最后乘法原理统计答案。 本蒟蒻还被边界孙了甚久。 1234567891011121314151617181920212223242526272829303132...