21.6.18 考试小记

发布于 2018-06-21  2.41k 次阅读


刚从NEYC回来,才发现好久没写题解了。

T1

维护一个集合,支持插入一个数、删除一个数、全局加x(<=1e9)、查询二进制第k位为1的数有多少个。

我们只需要对值域开k个桶,每个范围是[0,2^k - 1],然后最高为为0或1的各占一半,我们只需要维护桶里元素个数就好了,用树状数组的话复杂度O(nk^2)。

 

T2

原题,不过考场被卡常了,刚好多了几十ms,加个记忆化跑的飞快(其实是忘了)。

参见这里

 

T3

求n个点的无向图的联通块个数的k次方的期望。

考场上打的O(n^2logn)的NTT暴力,期望30,但第一个点WA了,可能是没特判K=0,也可能是别的边界。

正解做法比较神,假设我们有T个联通块,那么用斯特林数展开:

$$T^k = \sum _{i=1} ^{k} S(k,i) C(T,i) i!$$

之后,我们发现如果对于每个T都求的话,复杂度不能继续优化了,那么我们就尝试把T换掉。考虑这个式子的实际意义,其实是枚举非空集合的数量并分配元素。那么我们就可以把C换掉,也就是枚举点集,统计包含这样的特征的点集的图的个数,而这个玩意我们可以DP求。

首先求出f(n)表示n个点的带标号联通图的生成函数,g(n)表示n个点的任意无向图的方案数,那么\(g(n)=2^{C_{n}^{2}}\),\(f(n)=g(n) - \sum_{i=1}^{n-1}C_{n-1}^{i-1}f(i)g(n-i)\)。我们可以多项式求逆,求出所有的f。

设\(G=\sum_{i=0}^{n} \frac{g(i)}{(i-1)!} x^i \),\(F=\sum_{i=0}^{n}\frac{f(i)}{(i-1)!}x^i\),\(H=\sum_{i=0}^{n} \frac{g(i)}{(i)!} x^i \),那么有\(G-F=FH)\,这样就可以搞了。

设\(g_{i}(n)\)表示i个联通块的生成函数,那么对于i >= 2,有如下转移:

$$ g_{i}(n) = \sum_{j=1}^{n} C_{n-1}^{j-1}\,g_{1}(j)\,g_{i-1}(n-j)$$

接着,由于我们只需要求出来小于等于K个联通块的结果,所以我们就卷出来所有的g就好了。

最后,答案就是\(\sum_{i=1}^{k} S(k,i) i! \sum_{j=1}^{n}C_{n}^{j} g_{i}(j) 2^{C_{n-j}^{2}} \),再卷出来所有的答案数组,我们的预处理就做完了,复杂度O(nklog(n)),单次回答询问是O(k)。

一定要记得特判K=0。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974