考虑差分. b1=a1,bi=ai−ai−1,bn+1=m−anb_1=a_1,b_i=a_i-a_{i-1},b_{n+1}=m-a_nb1​=a1​,bi​=ai​−ai−1​,bn+1​=m−an​. 对于bib_ibi​%333来说. 显然除了第111项和第n+1n+1n+1项可以是任意模3为0/1/23为0/1/23为0/1/2中的一个外.其他只能是1/21/21/2. 通过bn+1b_{n+1}bn+1​调节最大值的大小. 然后可以通过枚举b1,bn+1b_1,b_{n+1}b1​,bn+1​,枚举1/2{1/2}1/2的数量来确定另外一个的数量. 比方说我枚举111的数量为ccc...

在利用卷积使得各项相乘的时候,由于顺序会被交换,所以b数组要倒序输入,可以看成是两个卷积之间的配对. 画个图就懂了~ code: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=4e6+5; const int mod=998244353; const double pi=acos(-1); struct cp{ double x,y; cp(){x=0,y=0;} cp(double X,double Y){x=X,y=Y;}; }f[N...

与多重集的排列数不同组合数即是不含有相同数交换的数. 并不是很难. Devu and Flowers 题面翻译 Devu 有 nnn 个花瓶，第 iii 个花瓶里有 fif_ifi​ 朵花。他现在要选择 sss 朵花。 你需要求出有多少种方案。两种方案不同当且仅当两种方案中至少有一个花瓶选择花的数量不同。 答案对 109+710^9+7109+7 取模。 1≤n≤20,0≤fi≤1012,0≤s≤10141\le n\le 20,0\le f_i\le 10^{12},0\le s\le 10^{14}1≤n≤20,0≤fi​≤1012,0≤s≤1014 题目描述 Devu wants to ...

数学不好的记录一下. 题目是给定R,G,BR,G,BR,G,B的数量.然后给你一个kkk,要求字符串中有kkk个RGRGRG的方案数. 考虑先放G,B,RGG,B,RGG,B,RG,最后补RRR. 考虑先放的方案数就是(numG+numB)!/(numG−k)!∗(numB)!∗(k)!(num_G+num_B)!/(num_G-k)!*(num_B)!*(k)!(numG​+numB​)!/(numG​−k)!∗(numB​)!∗(k)!. 多重集的排列,总的方案/内部随便排的方案数. 再然后考虑补RRR.RRR不能放在GGG的前面,我们可以做一个操作就是把含有GGG的向最近的B,RGB,R...

第一次自己写出700700700分的题!!! 记录一下. 首先能到iii位置后面的一定是满足iii后面的连续的maxmaxmax.这点很显然. 那么我们设置dpdpdp状态: fi,jf_{i,j}fi,j​为到了第iii个位置,值是jjj的方案数.注意这是从111开始数到iii考虑本质不同的序列.同时考虑后面的影响. 初值就很显然,就是后面能到111的所有值设置成111. 那么其实就有222种情况. 第一种情况是前面的值比我现在要大,但是它和我之间有个更大的,这种是不能转移的,很显然这种维护一个单调栈即可,单调栈内都可以转移. 第二种情况后面的值能覆盖到我当前的位子.这种值也在iii位置是存...

推介这篇博客吧,写的真的挺好的. 算了说点自己的理解吧... 首先fftfftfft是解决两个多项式相乘把时间复杂度从O(N2)O(N^2)O(N2)优化到O(N∗logN)O(N*logN)O(N∗logN).学它可以解决一些用前缀不能解决的优化. fftfftfft里面引进了复数,它是非常的妙的,无论是使得从多项式用系数表示转化成多项式用值来表示,还是用多项式用值来表示转化成多项式用系数表示. 假定我们知道两个多项式的系数表示,那么一定可以求出两个点在至少n+m+1n+m+1n+m+1点的值,为什么要求这么多呢,因为其实可以用脑子想想就okokok了,把多少次方全部看成未知数,那么nnn元...

大概这才是期望dpdpdp的入门题吧. 可以合并当前项的dpdpdp哦！ 首先定义方程fif_ifi​表示已经拿到了iii个,还需要拿多少次能全部拿完的期望. 那么容易得到转移方程: fi=fi∗(i/n)+fi+1∗(1−i/n)+1f_i=f_i*(i/n)+f_{i+1}*(1-i/n)+1fi​=fi​∗(i/n)+fi+1​∗(1−i/n)+1. 合并同类项可以得到: fi=fi+1+n/(n−i)f_i=f_{i+1}+n/(n-i)fi​=fi+1​+n/(n−i). 同时定义答案数组ansians_iansi​已经拿了iii个所需钱的期望,那么也可以得到方程. ansi=(i/...

是一种可以针对i j具有某种单调性来用斜率优化dp{dp}dp转移的一种方式. 例:BZOJ1010 玩具装箱toy 很容易的写出dpdpdp方程,令fif_ifi​表示解决前iii个的最小花费. 那么转移也很明显就是:fi=fj+(sumi−sumj−L+i−j−1)2f_i=f_j+(sum_i-sum_j-L+i-j-1)^2fi​=fj​+(sumi​−sumj​−L+i−j−1)2. 很显然复杂度是n2n^2n2的,如何优化呢. 斜率优化第一步假如是一次函数或许可以直接分析i,ji,ji,j得到单调性.但是这个是二次函数,二次函数可以分析前面两个的关系分析出单调性,比如说设j<...

一个很好的dp. 显然最优的方案一定是最瘦的情况,从前往后是没有转移性质的,也不符合dp的最优解转移. 那么考虑从后往前转移,定义: fif_ifi​表示到了第iii个的{最小宽度是多少,高度是多少},因为到了iii最小宽度的情况下,高度是最高的,顺带记录下高度即可. 转移很显然： fi.first=sufi−sufj,fi.second=fj.second+1{f_i.first=suf_i-suf_j,fi.second=f_j.second+1}fi​.first=sufi​−sufj​,fi.second=fj​.second+1。当sufi>=sufj+fj.firstsuf_...

kruskal重构树模板题 首先有三个等价的性质 我不会证! 图上任意两点的所有路径最大权值的最小值=最小生成树上任意路径的最大值=kruskal树上的lca. 就像不会sam一样 不过这个记着就行. 那么原问题就是按边的编号作为权值,查询两两之间的lca的val,最后用一个可以维护区间最值的数据结构得到答案. code: #include <bits/stdc++.h> using namespace std; const int N=2e5+5; const int M=20; int cnt=0; int fa[N],ch[N][2],f[N][M],val[N],dep...

AcWing 1174. 受欢迎的牛

千万不要把题目想复杂...一定要学会手推!!! 我们可以通过观察发现以下性质: 111.极值一定出现在端点. 222.对于出现的每个值我们可以进行差分. 然后可以进行手推发现另外一个性质: 考虑删除一个点对其他点的影响. 假如其他点id>posid>posid>pos,那么由公式可以推出该点的valvalval的变化是把valvalval变成了−>val−p[pos]+id−pos->val-p[pos]+id-pos−>val−p[pos]+id−pos. 然后根据它要小于等于mmm进一步推出:val+id−m<=p[pos]+posval+id-m...

一个很难的题目 写个博客加深印象. 首先可以把树划分成许多链 每个链可以分为0端和1端 有三个结论(可证). 1.0端和0端不能在一起 2.1端和1端不能在一起 3.中间点不能和别的端点在一起 除此之外其他都是合法的. so,把链划分dp转移可以得到答案. 定义dp状态: 0:表示为中间点 端点两个在子树内 1:表示为中间点 端点一个在子树内 2:表示为端点 端点不在子树内 3:表示为端点 端点在子树内 0/1端可以划分连通块 但是并不是一条链就是一个联通块 什么情况下才会产生边划分呢?显然端点相连不能产生连通块划分,只能属于两个不同的中间点相连才可以,我们把较高出的中间点进行划分. code...

区间+等差数列 区间求和 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5; const int mod=998244353; const int iv=(mod+1)/2; //维护区间+等差数列 以及 区间和. ll a[N]; struct Seg{ ll sum; pair<ll,ll>lz; }Tr[N<<2]; void pushdown(int u,ll l,ll r) { if(Tr[u].lz.se...