题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=6630

题目:


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. p1=x

2. pN=y

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.

Sample Input

3

4 1 4

4 2 4

100000 514 51144

Sample Output

2

1

253604680

 

解题思路:


对<p1=1,p2=n>符合条件的排列打表,打表结果如下:

可以发现f[i] = f[i - 1] + f[i - 3]

不难想出若左侧边界为3,那么可以确定的排列的一部分为:3 1 2 4,如右侧边界为7,可以确定的排列的一部分为:8 10 9 7

再对p1,p2分情况讨论,从特殊到一般总结规律:

(1)p1=1, p2=n:直接输出f[p2]

(2)p1=1,p2<n:

如p1=1, p2=7, 那么排列为:1 2 3 4 5 6  8 10 9 7 (红色字体表示这部分是固定的,加粗的红色字体表示对结果有贡献的排列的左右边界,下同)输出f[ (p2 - 1 )- (p1) +1] = f[p2 - p1]

(3)p1>1,p2=n:

如p1=3,p2=10, 那么排列为:3 1 2 4 5 6 7 8 9 10 输出f[ (p2)- (p1 + 1) + 1] = f[p2 - p1]

(4)p1>1,p2<n:

如p1 =3,p2=7,那么排列为:3 1 2 4 5 6 8 10 9 7 输出f[(p2 - 1) -(p1 + 1) - 1 ] = f[p2 - p1 - 1]

 

ac代码:


#include <bits/stdc++.h>
typedef long long ll;
const int maxn=100005;
const int mod=998244353;
using namespace std;
ll f[maxn];
void init()
{
    //一定要预处理出f[0]和f[1],不能省
     f[0] = 0;f[1] = f[2] = f[3] =1; f[4] = 2;
     for(int i = 5; i < maxn; i++)
         f[i] = (f[i - 1] + f[i - 3]) % mod;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    init();
    int t, p1, p2, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d %d", &n, &p1, &p2);
        if(p1 == 1 && p2 == n) printf("%lld\n", f[p2]);
        else if(p1 == 1 || p2 == n) printf("%lld\n", f[p2 - p1]);//<3,2,3> f[1]构成排列:2 1 3
        else printf("%lld\n", f[p2 - p1 - 1]);
    }
    return 0;
}