HDU 6630 permutation 2（找规律or推公式）

╰半夏微凉° 2021-11-08 16:18 256阅读 0赞

## 题意：给你n个数 1-n，给你其中两个做第一和最后一个数，相邻两个数的绝对值之差不超过2，将其他数填到序列里面，问有多少种填法。 ##

## 分析：找规律过的，可以抽象成一条链，每次可以往左/右跳一格或者两格，每个点只能跳一次，求x到y的路径数。画一画可以发现如果x左边有数字，那么x把左边访问完再回到x+1的路线只能有一条。访问y右边也同理。如果x左边要访问，访问完以后一定会回x+1，如果y右边有数，要访问完切回到y就必须先到y+1。那么问题变成：从1到n，每次可以向左/右跳1/2格，要访问所有中间点，求路径数。设dp\[n\]为这个问题的解，则dp\[n\]=dp\[n-1\]+dp\[n-3\]。各种情况讨论讨论。注意x和y相邻且左右都有数要输出0。参考[https://blog.csdn.net/qq\_43202683/article/details/98520815][https_blog.csdn.net_qq_43202683_article_details_98520815]。 ##

## 总结：下次碰到这么多人过的题，直接找规律就好了，没那么多人会推公式的。 ##

## 代码： ##

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

[https_blog.csdn.net_qq_43202683_article_details_98520815]: https://blog.csdn.net/qq_43202683/article/details/98520815