2019多校第五场 HDU6630 permutation 2（全排列，DP）

链接：HDU6630 permutation 2

题意：

给出正整数$N(2\le N\le 10^5),x,y(1\le x<y\le N)$

求有多少种$1$ ~ $N$的全排列满足下列条件（$p_i$代表全排列的第$i$个数）

1. $p_1=x$
2. $p_N=y$
3. 对于所有$1\le i<N$，有$|p_i?p_{i+1}|\le 2$

分析：

就是要找出以$x$开头，$y$结尾，且相邻元素差值（的绝对值）不大于2的全排列有多少个。

首先可以发现，开头处$1$ ~ $x$的排列方式是固定的，结尾处$y$ ~ $N$的排列方式也是固定的，而且可以发现，如果$x?=1$，$x+1$也固定，同理如果$y?=N$，$y?1$也固定。

那么我们只需要找出$x/(x+1)+1$ ~ $y/(y?1)?1$中未固定的数有多少种排列方式即可，而且并不需要关心是哪些数是未固定的，因为他们是连续的，所以只需要知道个数就行了。

对于一个初始排列：$1,2,3,4,?,i?3,i?2,i?1,i$

$dp[i]:$ 第$i$固定，前$i?1$个数未固定的排列方式的总数。

首先易知：$dp[1]=1,dp[2]=1,dp[3]=2$

第$i$固定，前$i?1$个数未固定，可以转移向两个状态：

1. 第$i?1$个数也固定，即转移到$dp[i?1]$
2. 第$i?1$个数和第$i?2$个数互调位置，那么第$i?3$个数一定得固定，即转移到$dp[i?3]$

所以得到状态转移方程：$dp[i]=dp[i?1]+dp[i?3](4\le i)$

以下代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2e5;
const LL MOD=998244353;
LL dp[maxn+50];
int main()
{
    int T;int N,x,y;dp[1]=dp[2]=1;dp[3]=2;for(int i=4;i<=maxn;i++)dp[i]=(dp[i-1]+dp[i-3])%MOD;scanf("%d",&T);while(T--){
    scanf("%d %d %d",&N,&x,&y);if(x>y)swap(x,y);if(x!=1)x++;if(y!=N)y--;if(y==x)printf("1\n");else if(y<x)printf("0\n");elseprintf("%lld\n",dp[y-x]);}return 0;
}