同步发表于 博客园
题目大意
对于满足以下要求的长度为 $n$ 的序列进行计数:
- 序列的值域为 $[1,k]$;
-
对于序列的任意位置 $p\in[1,n]$,可以找到至少一个 $i$ 满足 $p\in[i,i+k-1]$,且区间 $[i,i+k-1]$ 为一个 $1\sim k$ 的排列。
$n\le10^5,k\le100$
解题思路
其实原本题意不是这样的,试图描述正式之后好像更难懂了。
密码是一个长度为 $n$ 的序列。
密码由若干个 $1\sim k$ 的排列拼接而成,且拼接时,不同排列可重叠。
于是不妨设 $f_i$ 为最后一个完整排列的结尾是 $i$ 的方案数。于是可以列出转移式:
$$
f_i=\sum_{j=1}^{k}f_{i-j}\times g_{j}
$$
$g_j$ 即在一个 $1\sim k$ 的排列后接上 $j$ 个数,使得满足以下两个条件的方案数:
- $[j+1,j+k]$ 是一个 $1\sim k$ 的排列,
-
对于任意 $1<i<=j,[i,i+k-1]$ 不是一个 $1\sim k$ 的排列。
直接拿 $1,2,3\cdots k$ 来考虑 $g_j$ 怎么求,那么即要求一个 $1\sim j$ 的排列,对于任意 $i<j$,这个排列 $[1,i]$ 的前缀位置上不能是一个 $1\sim i$ 的排列,求满足条件的排列个数。
考虑容斥,首先令 $g_j=j!$,然后考虑减去不合法的,对于一个不合法的排列,它可能存在若干个前缀符合 $[1,i]$ 是一个 $1\sim i$ 的排列,那么我们枚举每一个不合法排列最后一个违反限制的前缀,在这个位置将其减去。
假设当前枚举到 $i$,首先 $[1,i]$ 这部分肯定是 $i!$ 种填法,而 $[i+1,j]$ 这部分,由于我们钦定 $i$ 是最后一个违反限制的前缀,故 $[1,i]$与 $[i+1,j]$ 相接不可再违反限制,即对于任意 $i<p<j,[i+1,p]$ 这一段上不能是将 $i+1\sim p$ 这些数任意排列的结果,于是就变成子问题了,乘上 $g_{j-i}$ 就好了。
所以就是两个简单的式子:
$$
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$ 就是答案了,然后这个题大概还可以搞什么矩阵快速幂或者线性递推,前者感觉没必要,后者我不了解,于是就到此为止了 QwQ。
1 条评论
[Solution][YZOJ50104] Password| Simple Counting – JIUYASHUIJING · 2022年5月3日 12:03 上午
[…] Published simultaneously in Mina! […]