9月做题记录

9月做题记录
最后一个9月份了,年份都不用写了;即使实力不强也希望这份题单能给后人一些帮助

这个月主要在做课件,整体质量不错

loj6338「SDWC2018 Day2」优秀CF301E Yaroslav and Arrangements

请先思考后再展开

先题目转化:

  1. 首先值可以平移到从1开始,然后乘上(m-mx+1)即可
  2. 拆环,在n+1处放个1

k很小可以放状态里面,明显计数dp
考虑从小到大插入数字,一开始一坨1,每两个1中间需要插2,每两个2又要插3
$f(mx,now,pp,cnt)$表示长度now,pp个空位,生成cnt个良好数列
转移枚举插入T个数,$f(mx+1,now+T,T-pp,cnt*C_{T-1}^{pp-1})+=f(mx,now,pp,cnt)$

code

CF947E Perpetual Subtraction

请先思考后再展开

生成函数做法
$$
考虑f(生成函数为F)转移到ff(生成函数为FF),通过化式子使其支持快速重复\\
FF=\sum_{i=0}^n(\sum_{j=i}^nf_j/(j+1))x^i=\sum_{j=0}^n \frac{f_j}{j+1}*\frac{x^{j+1}-1}{x-1}=\frac{\int_1^x F(t)dt}{x-1}\\
考虑设G(x)=F(x+1),GG(x)=\frac{\int_0^xG(t)dt}{x},gg_i=\frac{g_i}{i+1},每次操作可快速转移 \\
那么只需要考虑开始和最后同阶f和g怎么转化,\sum_{i=0}^n g_ix^i=\sum_{i=0}^nf_i(x+1)^i
$$
二项式展开+二项式反演+ntt,卷积方式和第一类斯特林log卷的方法类似,就翻转一下就好了,code
可见本做法的核心在于巧妙地构造G,得到一个很好用的转移式;这个做法并不是很好想,然而另一种做法更鬼畜……

线性代数做法

其实有了线性代数基础知识,并不难看懂Vectorxj题解官方题解scb的题解

然而这个特征值好推,特征向量不好推啊,似乎scb有有理有据的中文推导,然而并没有太大耐心去看了

51nod1229 序列求和 V2

题意:求$f_k(n)=\sum_{i=1}^n i^kR^i$

请先思考后再展开

$$
(R-1)f_k(n)
=n^kR^{n+1}+\sum_{i=1}^n R^i((i-1)^k-i^k)二项式定理\\
=n^kR^{n+1}+\sum_{i=1}^n R^i(\sum_{j=0}^{k-1} C_k^j i^j(-1)^{k-j} )
=n^kR^{n+1}+\sum_{j=0}^{k-1} (-1)^{k-j}C_k^j \sum_{i=1}^{n} i^j R^i\\
=n^kR^{n+1}+\sum_{j=0}^{k-1} (-1)^{k-j}C_k^j f_j(n),可以O(k^2)递推
$$
记得R=1要特判,自然数幂和

51nod1822 序列求和 V5

这题不建议开

请先思考后再展开

R=1先判了,要求$O(k)$可以插值或伯努利,详见这里

实话说,本题的做法几乎每一步除了神还是神,我只能理解其正确性,而没法逻辑上推导,见谅。

$$
1)f_k(n)=R^{n}F_k(n)-F_k(0),这里F_k是个k次多项式,正确性很好证明,上面的递推式+归纳法即可 \\
那么我们现在的目标就是求出F_k的点值然后插出来,再探索一些关系 \\
2)f_k(n+1)-f_k(n)=(n+1)^k R^{n+1},这个也是上面的递推式+归纳法可证 \\
同时f_k(n+1)-f_k(n)=R^{n+1} F_k(n+1)-R^nF_k(n),可得F_k(n+1)=(n+1)^k+F_k(n)/R即递推式 \\
3)根据牛顿插值法或自行思考一下,任何关于x的k次多项式都可以被表示为\sum_{i=0}^k a_i C_x^i,也可以看做系数放了分母的下降幂多项式 \\
\sum_{i=0}^{k+1} (-1)^i C_{k+1}^i F_k(i)
=\sum_{i=0}^{k+1} (-1)^i C_{k+1}^i \sum_{j=0}^ka_jC_i^j
=\sum_{j=0}^ka_j(\sum_{i=j}^{k+1} (-1)^i C_{k+1}^i C_i^j=0)=0 \\
证明:\sum_{i=j}^{k+1} (-1)^i C_{k+1}^j C_{k+1-j}^{i-j}
=\sum_{t=0}^{k+1-j} (-1)^{j+t} C_{k+1}^j C_{k+1-j}^{t}
=C_{k+1}^j (-1)^j (\sum_{t=0}^{k+1-j} (-1)^t C_{k+1-j}^{t}=[j=k+1]=0)=0 \\
4)于是我们获得了k+1条方程,能求出至少一组解,点值数量也超过k \\
设A=F_k(0)然后表示出F_k(1..k+1)从而求出A,然后用2的递推式求出点值,再插值即可
$$

总复杂度$O(\sum k)$

uoj193「UR#14」人类补完计划

题意:给出一个n个点m条边的无向图,求所有基于边集的生成子图是一棵连通基环树的方案权值和,一个方案的权值为$2^{非叶子节点个数}$

请先思考后再展开

Rose的做法:和CEOI2019游乐园有点像,一定要分清哪些东西你需要考虑进容斥系数的选择而哪些不用

$$
首先考虑环,不妨从编号最小的点开始,这样每个环会记两次,设link(S,ed)然后转移到比mi(S)大的点,O(2^nn^2)\\
f(S)表示连通基环树方案数,用link(S)/2初始化,设cnt(T\to S \setminus T)边方案,可以用类似游乐园的方法O(1)处理切换 \\
f(S)=\sum_{T\ne \emptyset,T\subset S} (-1)^{|T|+1}f(S \setminus T)*cnt(T\to S \setminus T),ans=\sum_{S} \sum_{T\subset S可空} pp(|S|,|T|) 2^{|S|-|T|} f(S \setminus T)*cnt(T\to S \setminus T) \\
我们希望2^{n-i}=\sum_{j=0}^{i} C_i^j pp(i,j)*2^{n-j},即1=\sum_{j=0}^{i} C_i^j pp(i,j)*2^{i-j},考虑pp(i,j)=(-1)^j,O(3^n)
$$
低级推广一下,设权值为$a^{非叶子个数},则pp(i,j)=(1-a)^j$即可

至于官方题解的做法能进一步怎么推广并没有细看,感兴趣的可以看看,另外还有zx的$2^nn^3$做法

luogu5162 WD与积木

请先思考后再展开

难受,又被教做人……脑子是个好东西,我也想要一个

比较直接的思路:$ans=\frac{f_n=\sum_{i=1}^nS_2(n,i)i!*i}{g_n=\sum_{i=1}^n S_2(n,i)i!}$ ,然后就止于$O(Tnlogn)$了

换个思路,考虑dp,$g_n=\sum_{i=1}^nC_n^ig_{n-i}+[n=0],f_n=g_n+\sum_{i=1}^nC_n^if_{n-i}$

妈呀这居然变成生成函数裸题了……$G=e^x*G-G+1,G=(2-e^x)^{-1};F=G+e^xF-F,F=(2-e^x)^{-2},O(nlogn)$

uoj50「UR #3」链式反应

请先思考后再展开

是我鲁莽了……以为不搞有根树就行了,$F=x(F^2G/2+1)$,仔细想想才发现是错的,还是应该老老实实从dp式开始写
$$
f_n
=[n=1]+ \frac{1}{2} \sum_{t \in G} \sum_{i=1}^n C_{n-1}^{t} C_{n-t-1}^{i} f_{i} f_{n-t-i}
=[n=1]+(n-1)! \sum_{t \in G} \frac{g_{n-t-1}}{t!},g_n=\frac{1}{2} \sum_{i=1}^n \frac{f_if_{n-i}}{i!(n-i)!}
$$
到这里已经可以分治FFT了,$O(nlog^2n)$,rk1和2似乎都是这个做法,这种自己卷自己的分治FFT不会写见yyb的code这里

接下来介绍一种理论复杂度nlogn的做法

写成生成函数就是:$\frac{d}{dx} F=1+F^2G/2$,也就是一个一阶微分方程(接下来符号换来换去的……f是函数,F是形式幂级数,B是这一层的,b是上一层的)

即现在已知常多项式G,已知函数$f(b)=Gb^2/2+1$,求解$\frac{d}{dx} B=f(B)$;考虑怎么给牛顿迭代修锅

详见生成函数-解微分方程,代码咕了

AGC018E Sightseeing Plan

题意补充:在给定3个无交矩形内选3个点,对「连接3点路径数」求和

请先思考后再展开

$$
设f(a,b)表示从(0,0)\to(a,b)的方案数,显然f(a,b)=C_{a+b}^a \\
于是 \sum_{x=X_1}^{X_2}\sum_{y=Y_1}^{Y_2} f(x,y)=f(X_2+1,Y_2+1)-f(X_2+1,Y_1)-f(X_1,Y_2+1)+f(X_1,Y_1) \\
枚举4*4种关键点选择方案,问题转化成统计(0,0) \to (dx,dy)的路径权值和,一条路径的权值为与矩阵([X_1,X_2],[Y_1,Y_2])的交的长度 \\
注意到这个长度其实就是在矩形中的终点T与起点S的哈密顿距离,T_x+T_y-S_x-S_y+1
$$
然后这个东西是可以拆开计算贡献的,考虑会被作为起点多少次即可;而且起点终点关键点只有$4e6$个

CF286E Ladies’ Shop

题意:现在有序列a,问是否存在序列p满足对p做值域m以内的完全背包后=a

请先思考后再展开

又被教育了是什么鬼啊……虽然暴力多项式快速幂应该能过,但存在nlogn做法

首先「有解」与「a是解」是等价的,如果无解则a也不是解;那么我们现在只需要知道是否存在一个k使得能被a表示而不在a中;考虑第一个这样的k,你发现一定$\exists i,j\le n,a_i+a_j=k$,因为比k更小的不在a中的数都是不可表的;于是我们对a做多项式平方即可判断是否无解。

考虑最小的p,这个p一定是a的子集(剩下类似NOIP2018D1T2),对于每个数「在p中」等价于「不可被前面的表出」,思考一下发现也是一定$\exists i,j\le n,a_i+a_j=a_t$,因为已经保证有解了,那么如果需要超过两个数表示(可能有重复,不关心怎么组成),那么那些数的子集和一定都是a中的;于是对a做多项式平方即可。

$O(mlogm)$

Topcoder SRM613 TaroCheckers

题意:n行m列的棋盘,放允许超过2n个棋子;每行的前lefti和后righti都要各放恰好一个棋子,且每列最多一个棋子,问方案数;$n \le50,m \le 200,left_i+right_i \le m$

请先思考后再展开

考虑从左往右处理每列,设$f(i,a,b)$表示处理了i列,有a列可用,有b行需要处理right

转移的时候,可选择把这一列放在b个行中;另外如果这一列是k个left的终止位置,则需要在剩下的a中选择k个

$O(m^2n)$,code

Topcoder SRM625 Seatfriends

题意:有一张N个带标号位置的圆桌,现在有K个无标号人按顺序来坐下,左右相邻将产生连通块,要求任意时刻不超过G个连通块,问分配方案数。$N,K,G\le 2e3$

请先思考后再展开

这题牛皮

先看K人无区别,设$f(m,k)$表示m个人划分为k个集合,然后我们先不考虑空位,等划分完后再插入,这样是对的

$合并f(m+1,k-1)、单独f(m+1,k+1)+=f(m,k)*k,两侧f(m+1,k)+=f(m,k)*2k$;

$ans=N\sum_{k=1}^G f(K,k)C_{N-K-1}^{k-1}$,也就是旋转圆排列、剩下N-K个空格划分为k个非空组

$O(KG)$,注意要特判N=K的情况;code

loj547「LibreOJ β Round #7」匹配字符串

请先思考后再展开

会28pt不会52pt的制杖估计只有我了吧……$f_i表示以0结束=\sum_{j=i-m}^{i-1}f_j,常系数递推O(m^2logm)$

注意到模数小的跟死者一样,那我们可能需要推个式子,基本都能很方便地计算,问题是怎么推

上面已经有了一个跟m相关的算法,考虑数据分治,看看能不能搞个n/m的

你可以直接容斥,为了保证不重叠前面加个0,$ans=\sum_{i=0}^{n/(m+1)} (-1)^i 2^{n-(m+1)i} C_{n-(m+1)i+(i+1)-1}^{(i+1)-1},O(n/m)$

题解给出了一种有趣的思路,考虑上面的递推式,注意到上面的递推式系数与i无关

设$s_i=\sum_{j=1}^i f_i,s_i-s_{i-1}=s_{i-1}-s_{i-m-1},s_i=2s_{i-1}-s_{i-m-1},s_0=1$

考虑一个巧妙的题意转化:i连向i+m+1一条-1,连向i+1一条2,路径权值为边的积,求0到n权值和

枚举用了多少个长边,也能得到上面的式子

$当n=2^{36},m取2^{11},min(m^2logm+n/m)可通过本题$,感觉没必要像题解那样写全家桶

至于zyy的$O(m^3logm)$的矩乘代码,其常数应该是小到了非常夸张的地步

bzoj5058 期望逆序对

题意:对初始序列任意交换两个不同的数k次后所有方案逆序对和

请先思考后再展开

考虑只关注A和B两个位置(不失一般性认为上面现在就是A和B),然后你发现对于另外的某个元素C,所构成的所有情况种类(见下)与具体哪个C无关,因为任何一个C此时在哪里对我们现在关注的东西、操作没有任何影响;那么对这些状态做矩乘预处理操作k次的转移矩阵(矩阵不是自己写的,故用行向量,大概理解意思后自己推即可,写代码推也行)

$$
A=C_{n-2}^2*E(单位矩阵)
+
\left[\begin{matrix}
0 & n-2 & 1 & 0 & 0 & n-2 & 0 \\
1 & n-3 & 0 & 1 & 1 & 0 & n-3 \\
1 & 0 & 0 & n-2 & n-2 & 0 & 0 \\
0 & 1 & 1 & n-3 & 0 & 1 & n-3 \\
0 & 1 & 1 & 0 & n-3 & 1 & n-3 \\
1 & 0 & 0 & 1 & 1 & n-3 & n-3 \\
0 & 1 & 0 & 1 & 1 & 1 & 2(n-4)+1
\end{matrix}\right] \\
转移:
\left[\begin{matrix}
(A,B)&(C,B)&(B,A)&(C,A)&(B,C)&(A,C)&(C,C)
\end{matrix}\right]*A \\
设f(State)表示这种情况的系数,考虑到初始矩阵为[1,0,0,0,0,0,0],f(State)即第一行系数
$$

然后枚举每个y作为B,考虑每种情况的系数,$ans=\sum_y g_y(State)f(State)$;

这部分搞了很久没看懂别人写的题解,按自己的理解想了个就过了qwq
$$
g(A,B)=\sum_{x<y,a_x>a_y},g(B,A)=\sum_{x<y,a_x<a_y} \\
然后涉及C的,上面统计的是所有C而现在是具体的,所以g_y(State)/=n-2 \\
g(C,B)=\sum_{x<y}\sum_{i \ne x,a_i>a_y},g(B,C)=\sum_{x<y}\sum_{i \ne x,a_i<a_y} \\
g(C,A)=\sum_{x<y}\sum_{i \ne y,a_i>a_x},g(A,C)=\sum_{x<y}\sum_{i \ne y,a_i<a_x} \\
最后再计g(C,C)=C_n^2/2*f(C,C),因为所有可能的合法C之和恰为1/2 \\
$$
上面的条件非常好维护,搞个树状数组维护$x<y且a_x<a_y$的个数即可,$O(nlogn)$,code

uoj390「UNR #3」百鸽笼

注意只有小写n,并没有保证总和在30以内,上面的大写N是没用的……

请先思考后再展开

好题,正解复杂度均为$O(n^3m^2)$,前置:PKUWC2018猎人杀的题意转化

现在求第k列的答案,考虑容斥,固定至少m个非法列在第k列放完后仍未满
$$
我们只关心固定列,设形成一个长为L的序列,则最后一个元素一定是k\\
然后考虑每在这个序列上填一个数字,非固定列的贡献=\frac{1}{n} \sum_{i=0}^{\infty} (\frac{n-m-1}{n})^i=(m+1)^{-1} \\
F_k=\frac{x^{a_k-1}}{(a_k-1)!} *
\prod_{t \ne k} (1+y\sum_{i=1}^{a_t-1} \frac{x^i}{i!}),
ans_k=\sum L!*(m+1)^{-(L+1)}*(-1)^m *[x^L y^m]F \\
设f(L,m)=[x^L y^m]F,插入某列是O(状态n^2m*转移m),那么无脑每次都放进去是O(n^4m^2)的 \\
注意到对于求ans_k,我们其实是把其他n-1个卷起来,那一开始卷好n个后面删除掉k就行了 \\
复杂度降低至O(n^3 m^2),其中删除从背包撤回角度比较好理解 \\
$$
至于生成函数做法,我觉得难度、实现、本质上都差不多,就是推导的时候繁琐一点,因为我们在很早前就把式子里的n给消掉了,至于展开$x^Ae^{Bx}$对普通生成函数的贡献见这里的推导:AGC038E - Gachapon

HDU5181 numbers

题意:1到n依次入栈,给出m个限制,$A_i 要早于 B_i 出栈$,求多少合法出栈序列,$n \le 3e2$

请先思考后再展开

入栈出栈序列是可以表示为树形结构的,节点x的子树大小为k,则表示x先入栈,然后子树内的元素为$[x,x+k-1]$且都更晚入栈更早出栈。根据这棵树考虑一下条件$(A<B)$,当$A<B等价于A+siz_A-1<B$;当$A>B等价于B+siz_B-1 \ge A$

那么就可以做dp了,$f(x,k)表示以x为根子树大小为k,枚举最右边的子树大小,f(x,k)=\sum_{left=1} f(x,left)*f(x+left,k-left)$,每次做完一个点就把他的非法状态清零

本质上就是区间dp,$O(n^3)$,code

loj6041「雅礼集训 2017 Day7」事情的相似度

请先思考后再展开

首先各种做法复杂度都是$O(nlog^2n)$

这题在外面天马行空了1h,有许多idea可惜没肝出来,回来看了看题解表示有道理,再仔细想想发现我的做法改改就是对的了

这个做法没在网上见到,个人认为是最自然的,分享一下:

翻转字符串sa排序后缀,经典套路并查集从大到小合并,连通块存set启发式合并

set存储的是下标而不是排名,合并的时候考虑贪心,用set找到左右两侧新产生的关键点对,共有$O(nlogn)$个

一种思路是存下来作为一个点,那么询问就是要回答矩形最大值,这个离线就是经典的树状数组做

另一种思路复杂些(我脑残了),用「树上最短路」那题的思想,区间放到线段树上,现在对于一个区间要找到所有包含它的区间并删除,考虑用左端点单点查询找到包含左端点的所有区间,每个区间在当初插入的时候按右端点从小到大vector存,这样每次判vector最后的并删除掉,这样每个区间会被访问log次

code,这个做法是卡在了存下标这个小trick,而这个恰好是没啥替代方式的按我目前的思路,其他基本都想到了

下面是两个网上的sam做法,看题的时候到这个翻转后询问后缀的就主要在想sa,因为做题少sam以前都是拿来处理子串信息的所以没怎么考虑过

做法二:sam,两个前缀的最长公共后缀就是其lca的len,树结构上set存right集合启发式合并,然后和上面类似

做法三:sam,考虑怎么真正利用树形结构,询问点x与前面的点的lca就是让x向上跳,碰到标记的时候处理,同时从贪心的角度覆盖经过节点的标记,发现这个过程就是个access;那么离线询问按右端点递增回答,每次查询左端点后面的最大值,因为没有删除可以用树状数组维护,access的时候顺便维护好标记即可。

HDU5822 color

请先思考后再展开

首先考虑给出的是有根树,那么所谓同构只需要考虑直接孩子间,可以用树hash搞,设$f(x)$表示以x为根的本质不同染色方案数,现在对每个同构的孩子等价类考虑,设其大小为a,因为同构每个孩子的染色方案数都是相同的,设为pp;现在等价于把a分成pp个可空组,即$C_{a+pp-1}^{pp-1}=C_{(n+pp-1)\%p}^a$,考虑到a的总和为n,直接暴力算即可

然后对于有向基环树,现在把有根树dp完后就是一个有向环,相当于一个大小为s的项链,每个珠子有颜色(hash值)和权值(方案数),每个珠子任选权值中的一个数,这东西的置换群是所有合法的旋转,合法当且仅当旋转前后珠子的颜色是对应的,设幅度a合法,则循环长度为$lca(a,n)/a$,循环节大小为$gcd(a,n)$,故根据polya定理可得$ans=\sum_{合法a} f(cir_a)^{gcd(a,n)}$;合法旋转可以用序列hash判定。

复杂度瓶颈为树hash的复杂度,怎么搞见「JSOI2016」独特的树叶

CF135E Weak Subsequence

洛谷翻译太抠脚了

正经翻译:给出字符集大小k和一个值w,求有多少字符串P(设长度为n)满足其最长的满足条件的连续子串s长度为w。条件为能在原字符串中选一个不是连续子串的子序列,使得其等于s。

请先思考后再展开

一些浅层的性质(大致递进):

  1. 若L合法,则L-1也合法;若L-1不合法,则L不合法
  2. 不存在w+1的合法串的充要条件:对于任意长度至少为w的子串(l,r),l-1的字符在左侧一定独一无二,r+1同理(没发现这一条,结果没一个题解看懂的qwq,还好rose救命)
  3. P的左边n-w个字符互不相同,右边n-w也是
  4. $n \in [w+1,w+k]$
  5. 合法的长度w的串s,一定是P的前驱或后继
  6. 以前驱为例,$\exists i \in [w+1,n],P[w]=P[i]$

你会发现可做了很多,分情况讨论下(建议自行画个图),主要思路是容斥

  1. $n-w<w,首先是(P_k^{n-w})^2(n-w)k^{w-(n-w)-1}*2$,容斥的话如果$w-(n-w)>1,则为-(p_k^{n-w})^2(n-w)^2k^{2w-n-2}$

    若为$w-(n-w)=1,这种情况最多一次,-\sum_{i=1}^k C_k^i*i*C_{k-i}^{2(n-w-i)} C_{2(n-w-i)}^{n-w-i}((n-w)!)^2$

  2. $n-w=w,(P_k^w)^2-P_k^w(k-w)P_{k-2}^{w-1}$

  3. $n-w>w,P_k^{n-w}P_{k-(n-2w)}^w$,容斥掉非法情况$-P_k^{n-w}(k-(n-w))P_{k-(n-2w+1+1)}^{w-1}$

code

CF995F Cowmpany Cowmpensation

请先思考后再展开

先写个dp式:$s(x,i)=\sum_{j=1}^i f(x,i),f(x,i)=\prod s(son,i)$,接下来展示两个优化至$O(n^2)$的做法

做法一:拉格朗日插值,code

考虑$f(x,i)$是一个关于i的多项式,考虑怎么理解

边界$f(leaf,i)=1$是个0次多项式,$s(leaf,i)$是个1次多项式,似乎最高次是子树大小?

$s(x,i)$这个前缀和显然也是i的多项式且次数=f次数+1,f由s转移就是若干个多项式卷起来,最高次之和=子树大小-1,成立

做法二:容斥,code

考虑离散化dp,即设j为选的数中第j大的值,然后用容斥来纠正不同数个数更小的非法情况

先用$O(n^2)$把离散化dp做完,设gi为恰有i个不同数,$g_i=f(1,i)-\sum_{j=1}^{i-1} g_j C_{i-1}^{j-1},ans=\sum_{i=1}^{min(D,n)} C_D^ig_i$

可见上面两个做法的dp部分是一样的

51nod1690 区间求和2

请先思考后再展开

注意到那东西很像卷积,但是跟长度相关

因为只求一个和肯定是考虑每对数的贡献,然后也不难想到把长度2的区间特判掉,剩下的就是奇数;感觉很可能就是像万径人踪灭那样,把数对卷积到中间点取。问题是怎么把长度去掉,如果没有质数这个限制,那么就讨论$i+j与n$的大小关系,看被统计次数是被左边还是右边统计分成两段,然后看到质数就感觉可能是没啥关系的,但没推出来qwq

其实上面已经把该想的都想完了,设s为质数前缀和,考虑数对i和j的系数,你发现就是个卷积了

$若i+j \le n,就是S(i+j-1)-S(j-i);若i+j>n,就是S(2n-(i+j)+1)-S(j-i)$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/8884.html
转载请注明出处,谢谢!