a.
首先容易发现要求的东西是个多项式快速幂，最终要保留x项。
暴力的做大约是2个$log$的。然后发现多项式的次数很低，所以可以考虑一些奇怪的东西（也许是套路？）。
将$P^{n+1}$求导，有两种方式，即复合函数求导和乘积的导数，然后根据这两个式子可以列出方程，然后可以递推出每一项系数。
复杂度$O(kx)$。
b.
首先容易发现，一个序列的贡献只和0或1出现n个的位置有关，所以可以枚举这个位置组合数算贡献。
然后观察可以发现相邻两个特殊位置之间贡献都是类似的，可以通过前缀和预处理出来。
但是这个贡献和k有关，所以并不能全部预处理。
由于k的和不大，所以可以发现k的全部取值也只有根号种，全部预处理出来即可。
c.
首先考虑k为奇数的情况，对于大小大于$k/2$的集合，显然要将他们选入一个单独的集合，那么然后将较小的集合塞进去。
由于$k<=n$，所以必然满足$C(n,x)>=C(n,k-x) (x>=k/2)$，所以可以将每个大小较小的集合都塞进大集合所在的集合里面。跑个二分图匹配就行了。
然后考虑k为偶数的情况，与上面不同的是，多出了$x=k/2$的情况，这一部分只能自己和自己配对，所以直接跑二分图匹配就没戏了。
然后就要解决一般图匹配问题，可以打带花树来解决，由于此题图很简单，所以随机算法也很优秀。