[HDU 6330]2019 HDU多校test5 permutation 2

permutation 2

题目链接
Problem Description

You are given three positive integers N,x,y.
Please calculate how many permutations of 1∼N satisfies the following conditions (We denote the i-th number of a permutation by pi):
1. p 1 = x 1.p_1=x 1.p1​=x
2. P N = y 2.P_N=y 2.PN​=y
3. f o r   a l l   1 ≤ i &lt; N , ∣ p i − p i + 1 ∣ ≤ 2 3. for\ all\ 1≤i&lt;N, |pi−pi+1|≤2 3.for all 1≤i<N,∣pi−pi+1∣≤2

Input

The first line contains one integer T denoting the number of tests.
For each test, there is one line containing three integers N,x,y.
1≤T≤5000
2≤N≤105
1≤x<y≤N

Output

For each test, output one integer in a single line indicating the answer modulo 998244353.

题目分析
先假设是从1跳到N,第N-1个位置可能是N-1或者N-2,当是N-1时，相当于从1跳到N-1.
N-1位置上是N-2时，N-2上必须是N-1不然N-1就跳不到了，那么N-3位置上也必须放N-3，因此就相当与从1跳到N-3
综上我们可以列出递推关系 f [ n ] = f [ n − 1 ] + f [ n − 3 ] f[n]=f[n-1]+f[n-3] f[n]=f[n−1]+f[n−3]
现在考虑从x到y
可以发现必须要先 从x到1再回来，从y到n再回来，
稍微试一下可以发现x走到1再走到x+1这总走法是唯一的
从y到n到y+1也是唯一的
那么就相当于从1走到(y-x+1)了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
#define MAX_V 1002
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const double PI=acos(-1);
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const ll mod=998244353;
const int maxn=1e5+5;
ll f[maxn];
int main(){
    int t;
    scanf("%d",&t);
    f[1]=f[2]=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);
        if(x!=1)    x++;
        if(y!=n)    y--;
        printf("%lld\n",f[y-x+1]);
    }
    return 0;
}