HDU - 6630 permutation 2

​ 求 $1\sim n$ 的满足以下条件的排列 $P$ 的个数:

  1. $P_{1}=x$
  2. $P_{n}=y$
  3. 对于所有的 $i\in [1,n]$ 有 $|P_{i}-P_{i+1}|\leq 2$

​ 不妨设 $x<y$(如果 $x>y$ 那就把排列 reverse 以下就可以了),我们肯定要遍历 $1\sim n$ 的,可以跳的距离为 $1$ 或 $2$,那么 $1\sim x$ 和 $y\sim n$ 的遍历方法只有一种,那就是先上升后下降(或者先下降后上升)并且跳的距离为2,这样才能保证能有去有回都遍历一遍。这样我们的计数就只在区间 $[x,y]$ 之间了。当然了,如果 $x=1$ 或者 $y=n$ 的时候,计数区间就变大了。

#include <bits/stdc++.h>

const int maxn = 1.1e5;
const int mod = 998244353;
using namespace std;

int n, x, y;
long long a[maxn] = {0, 1, 1, 1};

int main() {
    for (int i = 4; i <= 100000; i++)
        a[i] = (a[i - 1] + a[i - 3]) % mod;
    int T;
    scanf("%d", &T);
    while (T--)
        scanf("%d %d %d", &n, &x, &y), printf("%lld\n", a[abs(x - y) + (x == 1) + (y == n) - 1]);
}