7月1日计数题题解

"错的不是我,是这个世界"

时间暂定,月考加油

CF1043F Make It One

清芷:这不是最小覆盖吗

EI:这种问题一般都很本质,你转化出了dp就再想想

清芷:gcd莫反一下幂...

我:???

somebody:min卷积没有小于O(n^2)的做法

我:哦/kk

首先我们有个暴力的O(n^3)做法:硬点某个数一定要被选,然后dp一下, $f_S$ 表示S集合里的质因数都还在要都不在的最小选数个数

于是 $f_S=min_{j&i==j}f_{j}^f_{i^j}$ ,且 $f_0=0,if(visB)f_{S^B}=1$ 为初始态

然后您T了,虽然可以玄学贪心前面的硬点部分但是下面DP是很慢的QAQ

弱者就止步于此/kk

...等等?

你会惊人的发现这个S好像就么点啊,因为3e5以内最多质因数也就6个了

也就是说DP的复杂度其实不是O(n^2),而是一个很玄学的东西

~~那么我们是不是有什么做法就是玄学硬点然后暴力DP就过去了?~~

std:

考虑 $f_i$ 表示 $gcd==i$ 选k个数是否可行

k可以枚举,大小也就是7

然后考虑计算 $f_i$ ,需要容斥,设 $g_i$ 表示公约数为i的方案数

然后 $g_i={C^{k}_{cnt[i]}}$ ,cnt[i]表示i的倍数个数

这个好像和莫反确实有点联系qwq

$f_i=g_i-\sum_{k|i,k>i,k<n}g[k]$

CF451E Devu and Flowers

多重集容斥

首先考虑一个简单的问题,就是每个多重集有无穷多个(或者说大于我们要取得数)

这个相当于我们有m个0,然后每个集合要抢占其中一些0表示选了自己集合中多少个数

ans=C^{k-1}_{m+k-1}

然后现在这样干包括了一个集合选超过 $n_i$ 个的不合法方案,要剪掉QAQ

ans=C^{k-1}_{m+k-1}-\sum_{i<=n,n_i<m}{C^{k-1}_{m+k-n_i-2}}

为什么硬点一个集合至少选了 $n_i+1$ 是这个呢?相当于我们提前拿出 $n_i+1$ 个给这个集合,然后剩下的自由分配qwq

然后你会发现您减重了两个集合都选超过 $n_i$ 的不合法方案,所以要加回来,容斥下去就好了

CF568B Symmetric and Transitive

暂时搁浅

CF839D Winter is here

暴力计数是考虑长度为i的子序列的贡献,然后就是和T1差不许多啦

但是这样不太行QAQ因为复杂度是O(n^2)的,你发现T1是枚举了一个长度啊

那...能不能改改,变成 $f_i$ 表示约数为i的一些数构成子序列的总长度!

然后显然我们有 $f_i=2^{(cnt_i)}-1$ , $cnt_i$ 表示约数为i的数个数

然后 $g_i$ 表示gcd为i的数的........总长度

那么我们就有

g_n=\sum_{d|n}\mu(n/d)f(d)

所以搞出f, $\mu$ 就做完啦!

复杂度是 $O(nlnn)$ 瓶颈在于求 $cnt_i$

CF1097F Alex and a TV Show

月考爆炸来写博客QAQ

首先看完前两个操作感觉很亲民?

然后第三个就使我爆炸

看眼数据范围,1e5,1e6/jk但是值域只有7000

不会了

考虑bitset,因为是gcd所以考虑反演一下

$f_i$ 表示i作为约数的出现次数qwq,用bitset记录%2后的值

然后我们对于操作1就是把值的v的bitset赋给那个

而操作2就是两个bitset异或一下qwq

而操作3就是and一下

最后考虑怎么反推回每个数出现次数

g_n=\sum_{n|d}\mu (\frac{d}{n}) f(d)

对于每个值v,把μ(d|v)%2的值单独存一个bitset这个题就是and一下做完了

复杂度 $O(nv/\omega)$

CF1097D Makoto and a Blackboard

蒟蒻的想法:

把所有约数搞出来,然后考虑建图,问题变成了走k步的到某个点的方案数,可以矩阵乘法...

复杂度...n<=1e6还可以,因为约数个数是 $\sqrt{n}$ 级别的,而n^3可能也就跑个100

std:

我们显然有 $dp[i][j]$ 表示值为i,已经j次操作的概率是多少这个状态

但是i太大,所以考虑变成某个质因子的指数

N=\prod_i {p_i^{x_i}}

ans显然积性函数,所以

ans[N]=\prod_i{ans[p_i^{x_i}]}

然后求每个次幂的单独的ans

$dp[i][j]$ 表示 $p_i^i$ 已经进行了j次操作的概率

然后不难发现

dp[i][j]=\sum_s^{i<=s<=x_i}{dp[s][j-1]/i}

初始状态是 $dp[x_i][0]=1$

ans[p_i^{x_i}]=\sum_{l=0}{dp[l][k]*p_i^l}

就做完了qwq

复杂度很玄学?反正T不掉

夏晓光(loveJY)的博客

6月24日计数题题解