• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

在米娜同步发布!

题目大意

对满足以下要求的长度为\(n\)的序列进行计数:

序列的范围是\([1,k]\);

对于序列中的任意位置\(p\in[1,n]\),至少可以找到一个\(i\)满足\(p\in[i,i k-1]\),区间\([i,i k-1]\)是一个\(

\(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\),

对于任何\(1i=j,[i,i k-1]\)不是\(1\sim k\)置换。

直接取\(1,2,3\cdots k\)考虑如何求\(g_j\),那么就需要一个\(1\sim j\)的置换。对于任何\(ij\),这个置换\([1,i]\)

考虑到公差,让\(g_j=j!\),然后再考虑减去非法排列。对于非法排列,可能有几个排列,其中前缀\([1,i]\)是\(1\sim i\)。然后我们枚举每个违反限制的非法排列的最后一个前缀,并在这个位置减去它。

假设当前枚举了\(i\),首先\([1,i]\)这部分必须是\(i!\)填充方法,以及\([i 1,j]\)这部分,因为\(i\)是最后一个违反限制的前缀,所以\ ([I 1,I] \)和\([i 1,j]\)不能再违反限制,即对于任何\

所以有两个简单的公式:

\[g_i=i!-\sum_{j=1}^{i-1}j!\乘以g_{i-j}\\

f_i=\sum_{j=1}^{k}f_{i-j}\times g _ { j }

\]

\(f_n\)是答案,然后这个问题大概可以做点矩阵快幂或者线性递归的事情。前者感觉没必要,后者我也不知道,就到此为止QwQ。

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now