6月24日计数题题解

"纵使日薄西山."

省选爆炸qwq攒了一个周的计数题来整理一下吧!

给定k,你需要求出在k次交换下能够变成1~n排列的排列数,n<=21

my stupid solution

首先观察到一个排列能在k次交换下变成1~n就一定需要满足 $\sum(len_i-1)==k$ 其中 $len_i$ 为第i个循环的大小

然后我们可以对k跑一个整数划分,得到所有划分方案,然后问题变成求满足这个循环的划分方案的排列个数qwq

那么我们就可以使用组合意义得到答案为 $\frac{n!}{\prod(len_i)\prod(cntlen(len_i)!)}$

相当于我们先选数放进这些环里面,然后除一个 $len_i$ 求出每个环圆排列方案数,

再又发现多个相同的长度是一样的,除以 $cntlen(len_i)!$

std:

考虑dp,f[i][j]表示长度为i的排列交换j次才能到1~n

转移考虑 $f[i][j]=f[i-1][j-1]*(i-1)+f[i-1][j]$ 表示要么放入前些个排列中(即j位置放之前的数)然后需要多交换一次,要么j自己放在最后合适的位置

f[1][0]=1;

给出n个01串,问包含他们的最短母串是什么,n<=16

强化版是如果母串是环的话最短怎么办...

发现答案就是总串长-被覆盖掉的串长

考虑状压,记录下已经用过哪些串,然后结尾是串i

转移时考虑和i做一个匹配...然后不太行,因为我们可能会导致i串被完全匹配掉了然后我们就要找次大

但是转念一想如果我们保证不会有被完全匹配的怎么样呢?

发现可以把已经完全在另一个串中的串去掉然后继续再做,答案仍然一样

AT4352 [ARC101C] Ribbons on Tree

考虑容斥,S表示那些边被断,得到式子 $\sum_S{f(S)*(-1)^S}$

然后这个式子直接计算是不行的,考虑容斥dp优化直接计数的思路

具体就是我们把这个式子本质找出然后变成一个带容斥系数的可行DP方案qwq

发现就是随机给树上的点分连通块,然后问方案数

这个可以DP了, $dp[i][j]$ 表示点i的子树里i所在连通块大小为j的前提下方案数是多少

转移 $dp[i][j]=\sum_{v \in son(i),k<j}(dp[v][k]+dp[i][j-k])$

以及当 $k==0$ 时,转移为 $dp[i][j]=dp[v][0]+dp[i][j-k]$ ,这个容斥系数的-1再下面乘了

最后别忘了 $dp[i][0]=-\sum_{j}dp[i][j]*g(j)$ ,这里把他到父亲的边*-1了

g(i)表示i个点两两匹配的方案数,为135...*(n-1)

CF449D Jzzhu and Numbers

其实这个不是T4?

构造这个集合显然可以容斥,真的显然....

$ans=\sum_{S}{ (-1)^S * f(S)}$

f(S)表示至少包含S这些位的数有多少个,S是二进制下为1的是哪些位

然后你发现这个f(S)可以O(n),O(nV)你命没了

高维前缀和啊!!!为啥想不到?一下子快乐起来qwq

CF840C On the Bench

首先做出一步转化,就是假设 $A=B^2*C$ ,B是尽可能大的,然后让A=C

这样就相当于相等的数不能放在一起了

然后考虑容斥一下, $ans=\sum_{i=0}(f(i)*(-1)^{i})$ , $f_i$ 表示有至少i对相等的数相邻的方案数

然后我们可以考虑怎么求呢? $g_{x,i}$ 表示值为x的数绑定了i对相邻的方案数,总的方案数 $f_i$ 就是 $g_x$ 卷积起来即可

复杂度 $O(n^2)$

CF840E In a Trap

考虑分块,额,好像不是计数题

但还是写一下吧, $O(n\sqrt {n})$ 然后这个题根号分块显然不够优秀,所以我们可以 $O(n*2^8)$

$f[i][j]$ 表示点i向上走j步得到的最大值是什么

这个可以用trie解决,因为我们可以把从根到点i $0~255^ai$ 扔到trie树里面解决

最后如果u,v距离小于256就直接处理,否则根号分块

QAQ

Finished in 2020/6/26

"或许对于毁灭而言,这是最好的结局呢..."

"可他还是...."

"不要说了","订婚人"粉嫩白皙的脸庞上还仿佛有着晶莹的丝丝泪痕,但是面色却一点也不苍白,美丽的大眼睛里闪烁出坚毅如星的光芒,"他不会开心的."

就算众人不能释然与这一切,可焕然一新的生活就如擀面杖一般把他们碾向生存的道路上

"结束,往往是下一个开始的征兆哦...就算这和我的宗旨不太相符?"

夏晓光(loveJY)的博客

网络流相关复习