← 完整题目索引

PROJECT EULER · #0631

约束排列

Constrained Permutations

仅题目 · 待解原题 ↗

设 (p1p2…pk) 表示将 pi↦i 的集合 1,...,k 的排列。定义排列的长度为k;请注意,空排列 () 的长度为零。

将排列 P=(P1P2⋯Pn) 中排列 p=(p1p2⋯pk) 的出现定义为序列 1≤t1<t2<⋯<tk≤n,使得 pi<pj 如果和仅当 Pti<Ptj 对于所有 i,j∈{1,…,k} 时。

例如,(1243) 在排列 (314625) 中出现两次:一次作为第 1、3、4 和 6 个元素 (3465),一次作为第 2、3、4 和 6 个元素 (1465)。

令 f(n,m) 为长度至多为 n 的排列 P 的数量,使得 P 中不会出现排列 1243,并且 P 中最多出现 m 排列 21。

例如,f(2,0)=3,排列为 ()、(1)、(1,2),但不是 (2,1)。

您还得到 f(4,5)=32 和 f(10,25)=294400。

求 f(1018,40) 模 1000000007。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。