集训队相关

8/?

收录14年后的清华集训、集训队作业、CCFWC、CTSC

清华集训

「清华集训2014」玄学

请先思考后再展开

首先$(a,b)=ax+b$这种信息是可以快速合并的,但是不满足交换律

如果可以离线的话,可以直接线段树分治,$时间O(nlog^2n)-空间O(nlogn)$

如果模数是质数,$a \ne 0$的时候,我们可以通过求出前r个操作、前l-1个操作来得到中间的操作的二元组,可以用主席树实现,$a=0$的话可以额外维护个线段树,$时间O(nlogn)-空间O(nlogn)$

然而模数不是质数的话,本来想CRT,但发现需要额外的空间存每个质因子相关的信息,时空都乘上10,对于本身就大空间的主席树来说不太可行

通过上面这么多失败的尝试,我们发现实际上要求我们找到一种只有合并的做法

考虑对于时间分块,那么散块直接枚举,完整的块内会有$O(siz)$个不同的区间,区间内打的标记是相同的,回答询问可以通过二分找到具体影响这个位置的标记贡献,按照时间顺序合并标记即可,$O(\frac{chg}{T}*T^2+qes*\frac{chg}{T}*log T)=O(m^{3/2}*log \sqrt m)$

将分块换成线段树,修改只在插满的时候向上合并,询问的时候二分或lowerbound,$时间O(nlog^2n)-空间O(nlogn)$

code

「清华集训2016」如何优雅地求和

请先思考后再展开

关于连续点值,你可能需要对下降幂多项式有所了解,总之我们可以nlogn求出$f(x)$的下降幂形式

$$
特殊情况:\sum_{k=0}^nC_n^kx^k(1-x)^{n-k}=1 \\
a^{\underline b}(a<b)=0, Q(x^{\underline C})
=\sum_{k=C}^n k^{\underline C} C_n^k x^k (1-x)^{n-k}
=\sum_{k=C}^n k^{\underline C} \frac{n^{\underline C}*(n-C)!}{k^{\underline C}*(k-C)!(n-k)!} x^C x^{k-C} (1-x)^{n-k} \\
=n^{\underline C}x^C (\sum_{k=C}^n C_{n-C}^{k-C}x^{k-C}(1-x)^{n-k})
=n^{\underline C}x^C (\sum_{k=0}^{n-C} C_{n-C}^{k}x^{k}(1-x)^{n-k-C})
=n^{\underline C}x^C \\
f(x)=\sum_i a_ix^{\underline i},Q(f)=\sum_{i=0}^m a_in^{\underline i}x^i,O(nlogn)
$$

code

「清华集训2017」生成树计数

现在流行m=1e9,m相关复杂度的做法见这里

请先思考后再展开

首先要掌握Prufer序列,对于确定的d序列(deg-1),$(\prod a_i^{d_i})\frac{(n-2)!}{\prod d_i!}(\sum w(d_i+1))(\prod w(d_i+1))*(\prod a_i)$,其中$w(t)=t^m$;

如果先不考虑那个求和,用EGF卷积分配d,$F(z)=\sum \frac{z^i}{i!}*w(i+1),ans=(\prod a_i)(n-2)!*([z^{n-2}]\prod F(a_iz))$

多项式乘法看起来不是很好做?上个Ln,那么就是求$T=\sum ln(F(a_iz))=\sum (lnF)(a_iz)$,$ans=(\prod a_i)(n-2)!*([z^{n-2}]Exp(T))$

设$P=lnF=\sum p_iz^i,T=\sum p_iz^i(\sum_{j=1}^n a_j^i)$,求等幂和$f_s=\sum a_i^s$在这里,为$O(nlog^2n)$

现在考虑那个求和,等价于某个多项式中$w’(t)=t^{2m}$,设$(\sum (\frac{F’}{F})(a_iz))*\prod F(a_iz)$,这里F’不是求导而是改用w’,左边那个和上面一样是一个多项式同时求$a_ix$的求值的和,$PP=\frac{F’}{F},\sum pp_iz^i(\sum_{j=1}^n a_j^i)$,用刚才算出的东西就能求了

综上所述,化生成函数是基本功,求等幂和我以前觉得很高手但现在也觉得是基本功,对同一个多项式,多个x求值的和用等幂和来做,第一次碰见但感觉推广性很好可以作为套路;然后观察多项式乘法用ln去化也挺套路的。

那么对我来说新奇的地方主要在于:先不考虑求和这个思路、这种求和看做修改某一项这样再次化作多项式求和

总而言之这个做法推广性不错,给提出者好评,code

upd:

之前碰到一种处理带权方案数的方法$\sum w(d_i+1)=[y^1] \prod (1+w(d_i+1))$,能用的话就把上面提到的不套路的地方规避了

那么$F=\sum \frac{z^i}{i!} w(i+1)(1+w(i+1)y),ans=(\prod a_i)[z^{n-2}y]Exp(\sum (lnF)(a_iz))$,拆分$F(z)=F_0(z)+F_1(z)y$

二元组手动实现模$y^2$,求逆为$(A_0^{-1},-A_1A_0^{-2})$,求ln为$(0,A_1A_0^{-1})$,求exp为$(1,A_1)$;常数稍大,尚未验证正确性,有空搞

集训队作业

「集训队作业2018」三角形

这里

「集训队作业2018」复读机

请先思考后再展开

$$
\begin{aligned}
考虑EGF,ans&=(\sum_{i=0}^\infty [d|i]\frac{x^i}{i})^k n![x^n] \\
单位根反演&=\frac{n!}{d} (\sum_{j=0}^{d-1} \sum_{i=0}^\infty \frac{( \omega_d^j x)^i}{i})^k [x^n] \\
&=\frac{n!}{d} (\sum_{j=0}^{d-1} e^{\omega_d^jx}) {[x^n]} \\
分类讨论d(题中k)的值,&然后二项式展开来计算,然后把e^t还原 \\
k=2,ans&=\frac{n!}{2^k}(\sum_{i=0}^k C_k^ie^{(2i-k)x}) [x^n]=\frac{1}{2^k}\sum_{i=0}^k C_k^i (2i-k)^n \\
k=3,ans&=\frac{1}{3^k}\sum_{i=0}^k \sum_{j=0}^{k-i}C_k^iC_{k-i}^j (i+\omega_3^1j+\omega_3^2(k-i-j))^n
\end{aligned}
$$

code

「集训队作业2018R4」青春猪头少年不会梦到兔女郎学姐

题意:n种颜色的球,每种颜色有$a_i$个,问所有排列的贡献和,一个排列的贡献为,首尾相连成环后极大同色长度乘积,$m=\sum a_i \le 2e5,n \ge 2$

请先思考后再展开

似乎是myh搬自校内XSY3156,集训队爷的git:zzqwxh/myh);来口胡一下
$$
\\ 设g_{i,j}=i个球分j段,每段长度乘积的带权方案,考虑长度乘积的组合意义——在每个段选一个恰选一个球,直接dp为O(nm)
\\ 构造双射,看做有i+j-1个球,选其中2j-1个染色,第奇数个染色点其实是选的球,
\\ 第偶数个染色点是选的隔板,能唯一还原成每种方案且不会漏,因此g_{i,j}=C_{i+j-1}^{j+j-1}
\\ 首先考虑链要怎么做,ans=\sum_{序列c表示实际情况} (\prod g_{a_i,c_i})*(ways=i种颜色每种c_i个相邻不同的方案数)
\\ ways还是容斥=\sum_{序列b,c_i \le b_i} ( \frac{(\sum b_i)!}{\prod (b_i!)} )(\prod (-1)^{b_i-c_i} C_{b_i-1}^{b_i-c_i}),丢进去就是 \sum_{b} ( \frac{(\sum b_i)!}{\prod (b_i!)} )(\sum_c \prod (-1)^{b_i-c_i} C_{b_i-1}^{b_i-c_i} g_{a_i,c_i})
\\ 对每个i做FFT优化卷积,然后分治FFT将n个多项式卷起来,O(\sum a_iloga_i+mlogm*logn)
$$
环的话可能是种套路,类似最小表示法,因为我们其实算的是每种权值对应的方案数,所以在方案数这里修一修

就是从强制第一个第一个球为1且和最后一个球不同,最后位移乘m,这样每种方案会被计算$b_1$次,除掉即可

而且也是因为算的是方案数,「第一个球为1且和最后一个球不同」=「第一个球为1」-「第一个球、最后一个球为1」,第一种$b1-=1$,第二种$b1-=2$

WC

「WC2018」州区划分

请先思考后再展开

先预处理好每一种方案(用二进制表示)的可行性、总人口
$f(p1,k) \times sum^p(k)=\sum_{i|j=k} (f(p2,i)) * (okay(p1-p2,j) sum^p(j))$
因为是子集卷积,用fwt优化(有教程,第一维是二进制下1数量)

这东西你看起来需要做快速幂,但这样和暴力复杂度差不多了
不从快速幂的角度思考,想着是一个无限背包
保持前面的东西现在都是被fwt过的,那么你只需要枚举当前计算的p1,然后做出来当前的集合幂级数,然后Ifwt回去,把非法状态去掉,把分母补上去,再fwt回来
时间复杂度 $O(n^2 2^n)$

友情提示:判断合法性,记得要判断连通块数量……
code

「WC2019」数树

请先思考后再展开

首先y=1的8pt是送的

对于op=0,显然答案为$y^{联通块数}$,等价于只有部分A的树边能用,dfs搜联通块数或直接统计边数即可,code-36pt

对于op=1,$\sum y^{联通块数}=y^{n}\sum y^{-边数}$,如果想求出$f_k=恰k条边$,很自然考虑容斥$g_k=至少k条边=\sum_{t=k} f_tC_t^k$

二项式反演得$f_k=\sum_{t=k} (-1)^{t-k}C_t^kg_t$,求g就是拼接n-k个联通块,还是列出Prufer序列的式子,$n^{n-k-2}(\prod siz_i)$

那就是CF917D Stranger Trees,$O(n^2)$60pt;但注意到我们只需要求$\sum y^{-k}f_k$而不需要具体每个k对应,所以考虑带权容斥

这是个经典的幂形式的系数,不会推见这篇文章最底下,总之枚举集合至少为T时,系数为$(y^{-1}-1)^{|T|}$(y=1除外,要特判)

$ans=y^{n}n^{n-2} (Y=\frac{y^{-1}-1}{n})^k (\prod siz_i)$,直接树上背包,还是 $O(n^2)$;只需要解决这个乘积,考虑其组合意义就是保留某些树边,然后每个联通块内必须选一个点,于是直接树形$dp(x,0/1)$表示根所在的联通块目前放过球没有;$O(n)$,code-68pt

对于op=2,如果你无脑写出有根树的F0、F1之类的,式子会很复杂没法拉格朗日反演;果然还是要投奔Prufer大师

考虑一个确定的siz序列能对应的树,$(\prod siz_i^{siz_i-2})*(n^{n-k-2} \prod siz_i)^2(y^{-1}-1)^k=(Y=\frac{y^{-1}-1}{n^2})^k(\prod siz_i^{siz_i})(n^{n-2})^2$

橘势顿时明朗了,$F=\sum_{i=1}^{\infty} \frac{i^i}{Y} \frac{x^i}{i!},ans=y^{n}Y^nn^{2(n-2)}*nx^n$

$O(nlogn)$,code

整体来看,给非集选手送了很多分,而且只要你会prufer,并且会经典幂权容斥,那么就是你不会dp也很可能可以搞出op=2

CTSC

「CTS2019」随机立方体

请先思考后再展开

前置:套路集锦-树形结构-9,似乎我的推导比别人的短些?

明显容斥至少k个,然后是基本功:$设V=nml,ans=P_n^kP_m^kP_l^k*f_k$

$f_k$=通过分配k个极大数间大小关系,得出k个菊花的树上编号合法概率

考虑最大值也就是根的大小,易得$f_0=1,f_k=f_{k-1}*\frac{1}{V-(n-k)(m-k)(l-k)}$,先写了个log的80pt验一发,签到失败.jpg

其实就是要线性求n个数的逆元,见套路集锦-数学-4code

「CTS2019」氪金手游

请先思考后再展开

相当于给出一个基图是树的图,将时间填上去后,满足每个点的出现时间都早于子树内其他点

一开始看错题以为是内向树,遂写了个$\prod \frac{w_i}{子树和}$的暴力(套路集锦-树形结构-9),荣获爆零,签到失败.jpg

感觉还是有点妙的吧:即使有反向边,通过容斥,就能看做正向边或忽略成森林

于是$(-1)^k$容斥,做树形背包,存子树内大小即可,$O(n^2)$,code

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