自动搬运

查看原文

来自洛谷，原作者为

	OtterZ 刷题时间到！

搬运于2025-08-24 23:00:51，当前版本为作者最后更新于2024-11-21 14:04:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目

求有多少个全排列，使 $p_i\bmod p_{i \bmod n + 1} \le 2$。

要求长度为 $n(1 \le n \le 10 ^ 6)$。

引理

引理：每一个排列从一个位置开始环形遍历，可得到结尾分别为 $1,2$ 的单调下降序列拼合得到的全排列。

证：对于 $p_i < p_{i \bmod n + 1},p_i > 2$，有 $p_i \mod p_{i \bmod n + 1} = p_i > 2$，故而 $p_i > 2$ 时总有 $p_i > p_{i \bmod n + 1}$，而 $p_i < p_{i \bmod n + 1},p_i \le 2$，有 $p_i \bmod p_{i \bmod n + 1} = p_i \le 2$，由此可得，每一个排列从一个位置开始环形遍历，可得到结尾分别为 $1,2$ 的单调下降序列拼合得到的全排列，证毕。

动规

对于其中一个下降子序列，每个数前可接：

1. $i\times j$；
2. $i \times j + 1$；
3. $i \times j + 2$。

我们设 $dp_{i,j}$ 为两序列结尾较小值为 $i$，较大值为 $j$ 的对应排列数，根据 $\max\{i,j\} + 1$ 的插入情况可得到转移方程。

优化

再来一个引理

引理：设 $s_i = \{x|j \in N^+,x \bmod i \le 2 \text{且} x > i + 1\}$，有 $dp_{i,i + 1} = 1 + \sum_{k \in s_i}dp_{k - 1,k}$。

证：对于一个序列结尾为 $i$，另一个序列结尾为 $i + 1,i$ 前为 $k$ 时，$i + 2,i + 3,...,k - 1$ 此时在另一个序列上，即 $i + 1$ 前，此时得到一个合法结果，还有一个情况，即将所有 $x > i$ 放在另一个序列中也会得到一个合法解。

证毕。

基于引理的快速动规

我们要的答案为 $dp_{1,2} \times n$，根据引理得到的公式可 $\operatorname{O}(n\ln n)$ 得出，这样就解决了问题。

注意 $n = 1$ 的特殊情况和转移方程的范围判断与去重。

代码

#include<cstdio>
using namespace std;
int n,m,dp[1000009];
int ans;
#define mod 1000000007
int main(){
	scanf("%d",&n);
	if(n == 1){
		puts("1");
		return 0;
	}
	dp[n - 1] = 1;
	ans = 1;
	for(int i = n - 2; i > 0; i --){
		dp[i] = 1;
		for(int j = 1; j * i <= n; j ++){
			if(j * i > i + 1){ //(i,i + 1) -> (j * i - 1,j * i) 
				dp[i] = (dp[i] + dp[i * j - 1]) % mod;
			}
			if(j * i > i && j * i + 1 <= n && i > 1){//(i,i + 1) -> (j * i,j * i + 1)
				dp[i] = (dp[i] + dp[i * j]) % mod;
			}
			if(j * i + 1 > i && j * i + 2 <= n && i > 2){//(i,i + 1) -> (j * i + 1,j * i + 2)
				dp[i] = (dp[i] + dp[i * j + 1]) % mod;
			}
		}
	//	printf("%d\n",dp[i]);
	}
	printf("%d\n",1ll * dp[1] * n % mod);
}