E
模数不是质数。EXCRT?
考虑排好了前 \(i-1\) 个颜色,插入第 \(i\) 个颜色的方案数。定义 \(sum=\sum_{k=1}^{i-1}{C_k}\),由插板法得答案为 \(\binom{sum}{C_i}\)。把每种颜色的答案相乘即可。代码。
F
状压 DP,定义 \(f_{S}\) 为 \(T\) 中元素被选集合是 \(S\) 的方案数。枚举上一个填什么元素即可转移。显然由于部分状态本质是相同的,会有重复计数。
弄个 hash 记录状态对应的子序列,如果是本质相同的状态就不转移。复杂度 \(O(n2^n)\),常数巨大。
我们发现转移时出现了本质相同的状态等价于从序列中删去一个元素,又插入一个元素,且该序列不变。
那么删去和插入属于一个同色连续段,只对每个同色连续段中第一个字符进行转移即可。复杂度 \(O(n2^n)\),300ms 轻松跑过。代码。
G
待更。