permutation 2-蒲公英云

permutation 2

题目链接；http://acm.hdu.edu.cn/showproblem.php?pid=6630You 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):

p1=x
pN=y
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

对于每个题，如果实在没有思路，我们大可以模拟求解一组数据样例。在模拟的过程中发现规律，找到关键点。从而求解。
这个题目，给了我们三组样例，我们大可以模拟一下求解。
100000 514 51144
我们可以考虑这个序列应该如何填充。
首先，我们可以在第2个位置放515，516，513，512。
在考虑一下，如果在第2个位置放了515，那么我的第三个位置，就能放513，516，517。如果，我的第三个位置放了513，那我之后的位置绝对不可能放到516（相差大于2）去了。同理，第三个位置放了516，那我之后的位置绝对不可能放到513去了。
所以，证明了，我的第2个位置不可能放515，同理可以证明不可以放516。所以我的第2个位置只能放512。513一样可以证明不能放。
到这里，就很明显了。如果还不懂得可以继续自己模拟一下512之后的情况。
所以，我们整体的序列应该是
从514开始不断地往下放一直放到1。在不断地往上放，一直放到515。
从51144不断地往上放，一直放到100000，在不断地往下放，一直放到51143。
那么，序列的个数应该就是515到51143，这一段的可能数了。
我们可以继续像之前那样模拟考虑，
515之后可以放516和517。
如果放516，那么516的考虑同515。
如果放了517，那么接下来就只能先放516，在放518。那么此时518的考虑也同515。
此时很明显了。
515的次数等于516的次数+517的次数。
如此一直下去，我们可以想象最后放到51143的情况。
51143之前的那个数只能是51142和51141。
51142和51141放到51143的种数只有一种可能。
所以，很明显了。
51140 = 51142 + 51141的次数。
那么，我们就可以把这个当作一个递推式子来求解了。
同时，注意x为1的情况和y为n的情况。

#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
typedef long long ll;
#define mod 998244353
int T,N,x,y;
ll dp[100010];
void init()
{
    dp[0] = 1; dp[1] = 1;dp[2] = 1;
    for(int i = 3; i <= 100009; i ++)
        dp[i] = (dp[i - 1] + dp[i - 3]) % mod;
}
int main()
{
    init();
    scanf("%d",&T);
    while(T --)
    {
        scanf("%d%d%d",&N,&x,&y);
        if(x > y)
            swap(x,y);
        if(x > 1)
            x ++;
        if(y < N)
            y --;
        int len = y - x;
        printf("%lld\n",dp[len]);
    }
}