套路场.
涂色游戏
假设 $p_1\le p_2$ ,显然特判掉 $k=1$ 的情况后,只需要判断是否有 $\lfloor \frac {p_2-\gcd(p_1,p_2)-1}{p_1}\rfloor+1<k$ .
子序列问题
考虑组合意义,若 $[l,r]$ 内某两个数都是第一次出现的,那么这个数对就会对 $(f(l,r))^2$ 造成 $2$ 的贡献.
若某个数是 $[l,r]$ 内第一次出现的,这个数会对 $(f(l,r))^2$ 造成 $1$ 的贡献.
预处理出 $pre(i)$ 表示 $a_i$ 上一次出现的位置,枚举后面的数,考虑每个前面的数与它能对多少个区间造成贡献即可.
游戏
树形 dp 求出钦定选了 $k$ 组有祖先后代关系的匹配的方案数,二项式反演即可得到恰好选了 $k$ 组的答案.
设 $dp(x,i)$ 表示在子树 $x$ 中选了 $i$ 组有祖先后代关系的匹配的方案数,转移时就是一个树形背包.