刚从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。