cojR10

Source

commetoj R11

好题:E

D

请先思考后再展开

先想了想这题二分、可持久化并查集之类的,似乎都不太行,那就kruskal重构树,设边权为max 点编号即可

那么每次回答询问就是倍增跳到不能跳为止,然后回答子树积,这个拿个树状数组维护即可,$O(qlogn)$

坑点:权值可能一开始就超过mod,需要判0的次数

E

请先思考后再展开

这道题还是很可做的

注意到$n*m$小而b大,然后考虑到对于伤害和S敌人的分配方案,根据隔板法=$C_{S-1}^{n-1}$,S会很大但n不大,基于这个考虑把隔板分配到人中,也就是把隔板数作为卷积上标,分配到每种人中。设$F_k(x)$表示第k种的OGF,那么$ans=[x^{n-1}]\prod_k F_k^{a_i}(x)$,如果求出F的话,多项式求幂(系数放缩一下即可),复杂度为$O(nmlogn)$

当不放隔板的时候,即$F_k(0)=b_k$;然后隔板的话我们需要允许对于每个人伤害序列的末尾也能放隔板,特判掉$k=m时F_m^{a_m-1}(x)*Special(x)$即可。

对于造成多少伤害,$F_k(x)[x^i]=\sum_{j=i}^{b_k} C_j^i=C_{b_k+1}^{i+1}$,可以快速求;$Special(x)[x^i]=\sum_{j=i+1}^{b_m} C_{j-1}^i=C_{b_m}^{i+1}$

code

F

请先思考后再展开

前不久才研究过dag计数,但完全没状态,想到了把分母3提出来,却没看出$2^{T \to S\setminus T}=2^{in(S)-in(T)-in(S\setminus T)}$

想到这个直接子集卷积就好了,$O(2^nn^2)$

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