「517模拟赛1」ABC难题

Tips: 模数是 \(10^8+7\)

不妨令序列总长为 \(n\) ，包含 \(m\) 种不同的数字

发现存在 \(ABC\) 的子序列只需要满足最左边的 \(A\) 和最右边的 \(C\) 之间有一个 \(B\)

由于可能出现多个 \(ABC\) ，考虑计算不存在 \(ABC\) 的情况

那么可以枚举最左边的 \(A\) 和最右边的 \(C\) 分别为 \(X,Y\) ，那么需要不存在 \(ABC\) ，并且枚举的 \(X,Y\) 合法 的充要条件是

\([1,X-1]\) 中不存在 \(A\) ， \([X+1,Y-1]\) 中不存在 \(B\) ， \([Y+1,n]\) 中不存在 \(C\)

这三个限制，每一个限制会让一种颜色能够选择的字母数量-1

那么枚举 \(X\) ，扫描每一个 \(Y\) (注意不一定满足 \(X< Y\) )，同时记录每个数字是否出现在 \([1,X-1],[X+1,Y-1],[Y+1,n]\) 中

在每次扫描时改变限制，同步统计出受到 \(0,1,2,3\) 个限制的数字的个数，然后答案就是 \((3-i)^k\) 之积

然而这样还不够，因为可能根本不存在 \(A,C\) ，不存在 \(A\) 或者 \(C\) 的答案为 \(2^m\) ，同时不存在 \(A,C\) 的答案为 \(1^m\) ，容斥一下即可