Published simultaneously in Mina!

Topic

Counts sequences of length \(n\) that satisfy the following requirements:

  • The range of the sequence is \([1,k]\);

  • For any position in the sequence\(p\in[1,n]\), you can find at least one \(i\) satisfying \(p\in[i,i+k-1]\), and the interval \([i,i+k-1]\) is a permutation of \(1\sim k\).

\(n\le10^5,k\le100\)

Problem solving ideas

In fact, the original meaning of the title is not like this. It seems to be more difficult to understand after trying to describe it formally.

The password is a sequence of length \(n\).

The password is formed by splicing several \(1\sim k\) arrangements, and when splicing, different arrangements can overlap.

So let \(f_i\) be the number of the last complete arrangement ending in \(i\). The transitions can then be listed:

\[f_i=\sum_{j=1}^{k}f_{i-j}\times g_{j}
\]

\(g_j\) is the number of \(j\) followed by a \(1\sim k\) arrangement, so that the number of solutions that satisfy the following two conditions:

  • \([j+1,j+k]\) is a permutation of \(1\sim k\),

  • For any \(1

Take \(1,2,3\cdots k\) directly to consider how to find \(g_j\), then a permutation of \(1\sim j\) is required. For any \(i

Consider inclusion and exclusion, first make \(g_j=j!\), and then consider subtracting the illegal ones. For an illegal permutation, it may have several prefixes conforming to \([1,i]\) is a permutation of \(1\sim i\), then we enumerate the last violating prefix of each illegal permutation and subtract it at that position.

Assuming the current enumeration to \(i\), first \([1,i]\) This part is definitely a \(i!\) filling method, and \([i+1,j]In this part of \), since we decided that \(i\) is the last prefix that violates the restriction, so \([1,i]\)and\([i+1,j]\) can no longer violate the restriction, that is, for any \(i

So there are two simple formulas:

\[g_i=i!-\sum_{j=1}^{i-1}j!\times g_{i-j}\\
f_i=\sum_{j=1}^{k}f_{i-j}\times g_{j}
\]

\(f_n\) is the answer, and then this question can probably do any matrix fast power or linear recursion, the former feels unnecessary, the latter I don’t understand, so stop here QwQ.