C
code
本来不想写这**题的，但被坑死了（特判(n=0)时需满足(a_0=1)才有解）
跟官方题解有点不同，是逆推的，本质差不多
令(g_i)为第(i)层能向下伸的最大的个数，由于(sum a_i)不大，这个可以限制在long long范围内
然后从第(n)层逆推，令当前处理第(i)层，利用(g_i)将第(i+1)层的个数约束到第(i)层，然后再加上(a_i)
D
连边((i,p_i)(p_i
eq 1))，我们单独统计一个基环树的出现次数
这时图中出现基环树及树，对于每个基环树，不管其他边怎么连，其仍会出现，((n-1)^K)
现在统计若干个树并一起的方案数，考虑(m)个树，节点个数分别为(a_1,a_2,cdots,a_m)
则方案数为
- (m=1)：(a_1-1)
- (m>1)：((n-1)^{K-m}(m-1)!prod a_i)
E
结论1：先把(0)全部删完为最优解
若删了(1)，找后面的(0)去调整并不劣
考虑相邻两个(1)，产生的贡献永远固定，故我们可以将序列中所有的相邻(1)删掉，并计算贡献
那么问题就描述成不相邻的(1)所组成的序列
令某个位置的(1)前面有(p)个(0)，后面有(q)个(1)
- 当前位置为偶数：(leftlfloorfrac{p}{2} ight floor+q)
- 当前位置为奇数：(leftlceilfrac{p}{2} ight ceil+q)
通过下面操作可以达到上界
- 将前缀(0)全部删掉
- 从左往右将每个(0)区间删到仅剩(1)个
- 从左往右依次将(0)删掉
F
考虑合法序列的充要条件，对于(forall i,j(1le i<jle M))
按二进制为从高到低比较，第一个不相同的，若(a_i=1,a_j=0)，则之后的所有位必须相同
令((n,m))表示有(n)个数，共有(m)位的答案
- 若第(m)位在序列上形如：(000cdots 111)，即前面一段(0)后面一段(1)
则可以转移到((n,m-1)) - 若出现：(000cdots 01???01cdots 111)，即去掉前缀(0)与后缀(1)后，序列以首为(1)尾为(0)
则中间一段的之后的所有位必须相同，可以转移到((n-(len-1),m-1))。其中(len)表示中间那段序列的长度