permutation 2

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

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

 

算法：递推 + 思维

题解：你必须先考虑左端点和右端点，然后当左边和右边都填完了，之后便要x++，y--（是端点的话就不用），这是为什么呢就只有[x, y]个数了，然后填就有两种填法：x + 1 和  x + 2，之中x + 2就必须要返回填x + 1，再填x + 3，加上刚才的第一种可能 x + 1和第二种可能推出来的x + 3,这两个数又和最开始的x一样了，都又两种可能性，所以dp[i] = dp[i - 1] + dp[i - 3].

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 1e5+5;
const int mod = 998244353;

int dp[maxn];

int main() {
    dp[0] = dp[1] = dp[2] = 1;
    for(int i = 3; i < maxn; i++) {
        dp[i] = (dp[i - 1] + dp[i - 3]) % mod;
    }
    int T;
    cin >> T;
    while(T--) {
        int n, x, y;
        scanf("%d %d %d", &n, &x, &y);
        if(x > 1) {     //不是端点的话就自加自减
            x++;
        }
        if(y < n) {
            y--;
        }
        int m = y - x;      //计算[x, y]区间中数的个数，不包括x, y
        printf("%d\n", dp[m]);
    }
    return 0;
}