HN省集模拟赛第一场

A

求解长度为 \(n\) 的序列 \(A\) 数量，使得

• \(\forall i\in [1,n],A_i \in [1,m]\)
• \(\forall i\in [1,n),A_{i+1}\ne A_i\)
• \(\forall i\in [1,n-m+1],\{A_i,A_{i+1},\dots,A_{i+m-1}\}\ne\{1,\dots,m\}\)
• \(|\{ A_i\mid i\in[1,n]\}|=m\)

首先最后一个条件没啥用，我们可以二项式反演，令 \(f_i\) 表示 \(|\{ A_j\mid j\in[1,n]\}|=i\) 的序列数量。