首页 > itarticle > permutation 2

permutation 2

admin 11月 14, 2020 0

题目链接

题意

计算有多少种n的全排列，每两项之间的差绝对值都小于等于2，且第一个元素和最后一个元素分别为a,b。

思路

略微观察容易发现，1到a和b到n的元素位置其实只有一种可能，都是确定了的。（在纸上画一画就发现，如果这两边不先走，是构不成全排列的。）
那么我们要解决的就是中间这一段数字有多少种方法。
如1,2,3,4，其实只有两种走法，要么一个一个走，即1,2,3,4，要么1,3,2,4这样。可以推出一个简单的dp式子。

Code


using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const ll mod = 998244353;
ll f[maxn];

int ()
{
    int T;
    scanf("%d", &T);
    f[1] = 1;
    f[2] = 1;
    f[3] = 1;
    for (int i = 4; i <= maxn; i++)
        f[i] = (f[i - 1] + f[i - 3]) % mod;
    while (T--)
    {
        int n, x, y;
        scanf("%d%d%d", &n, &x, &y);
        int len = y - x + 1;
        if (x != 1) len--;
        if (y != n) len--;
        printf("%lldn", f[len]);
    }
    return 0;
}