【2022 NOIP 模拟赛 29】排列 做题记录

求满足以下条件的长为 $n$ 的排列 $p$ 的个数：

• 对于所有 $1\le i\le n-1$ 有 $p_i\operatorname{mod} p_{i+1}\le2$；
• $p_n\operatorname{mod}p_1\le 2$；

$1\le n\le 10^6$。

首先去掉 $1$ 和 $2$ 之后，完美的排列显然可以分成两段下降的序列 $A$ 和 $B$，它们之间需要用 $1$ 和 $2$ 拼起来。

观察到显然 $\{x,x-1,x-2,\dots,3,2,1\}$ 这样的一段连续序列一定是合法的，那么去掉 $1$ 和 $2$ 之后的序列 $\{n,n-1,n-2,\dots,5,4,3\}$ 一定可以分成若干段，第 $1,3,5,7,9,\dots$ 段分给 $A$ 并且互相连接，第 $2,4,6,8,10,\dots$ 段分给 $B$ 并且互相连接。

考虑动态规划，设 $dp_i$ 表示 $[i+1,n]$ 划分好了，最后一段以 $i$ 开头的方案数，那么考虑以 $i$ 开头的那一段前面是哪一段，有转移：

$dp_{i}=1+\sum\limits_{i|j}dp_{j-1}+dp_j+dp_{j+1}$

其中 $+1$ 是因为 $[i+1,n]$ 划分为一整段一定是合法的。

最后的答案即为 $2n\times\sum\limits_{i=1}^{n-1}dp_i$，因为 $[1,i]$ 这一段需要另外算，并且 $A$ 和 $B$ 可以任意交换顺序且环可以转。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector> 

using namespace std;

#define fio(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)

const int S=1000005,p=1000000007;

int n,dp[S];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

int main()
{
	fio("permutation");
	scanf("%d",&n);
	if(n<=2) return printf("%d\n",n),0;
	int ans=1;
	for(int i=n-1;i>=3;i--)
	{
		int tmp=1;
		for(int j=i;j<=n;j+=i) add(tmp,((long long)dp[j-1]+dp[j]+dp[j+1])%p);
		dp[i]=tmp;
		add(ans,dp[i]);
	}
	printf("%d\n",1ll*ans*2%p*n%p);
	return 0;
}