A. 染色问题

不然想到一个50分的dp，然而我的dp转移和正解不一样所以没法优化所以就死了。。要是用我的dp推正解大概只能考虑实际含义。

考虑每次在已有的颜色序列中间插入一段，那么考虑转移的方案数，不难得到一条dp转移路径的贡献是每次颜色序列长度+1的乘积。

所以枚举一共经过了多少次转移，转移次数为k的所有方案的贡献之和就是∏(x+i)的n-k次系数。

然后这个玩意直接分治可以做到2个log，考虑假如奇数那么暴力乘一项即可。

所以给另一半二项式定理展开就可以直接搞了。

B. 芬威克树

假如k是奇数，那么不难发现所有的转移都不会改变最低的k进制位，所以所有的转移方案形成了若干条链。

那么只需要在每条链的链头，也就是第一个数处维护整条链的信息即可。

考虑如何找到每个数对应的链头，由于每个点所属的链是可以确定的，并且可以知道当前点的前驱是谁，所以直接倍增就可以找到链头。

C. 礼物

类似周末晚会，这道题由于我当时写了个比较优秀的线性算法以为自己AC了。。。。然后发现恰好的限制没法处理，然后就当场暴毙了。

实际上，由于多了恰好的限制，通过dp预处理出方案数的方法已经不太可行了，所以大概要考虑当场算。

实际上是个比较套路的插板容斥，直接枚举至少多少区间不满足限制就行了。