【HDU 6630】多校第五场 permutation 2（找规律）

题目链接：传送门

题意：

T组测试样例，每组测试样例输入N，X，Y，N代表一个数组的长度，X代表数组的第一个数，Y代表数组的最后一个数，问排列1~N有多少种可能，并且满足 ，（1≤i<N） 。

思路：

由题意我们可以把x，y分为4种情况，即x=1且y=n，x=1但y!=n，x!=1但y=n，x!=1且y!=n这4种情况，下面分情况讨论：

① x=1且y=n

此时，可以得出排列的可能有a [ i ] = a [ i - 1 ] + a [ i - 3 ]种;

② x=1但y!=n（为了方便找出规律，假设n=7）

此时，多举几个栗子，你会发现y-1到n的数排列方式是确定的，只有一种，观察出此时排列的可能有a [ y - 1 ] 种；

③ x!=1但y=n （为了方便找出规律，假设 n=7）

此时，多列出一些式子，你会发现1到x+1的排列方式是确定的，只有一种，观察此时排列的可能一共a [ n - x ] 种；

④x!=1且y!=n（为了方便找出规律，假设 n=7）

观察此时分两种情况，若y = x+1，则排列为0；否则，排列一共有a [ y - x - 1] 种；

一个栗子不具有代表性，自己在做的时候可以多整几个栗子测试一下。

My  Code：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<algorithm>
#include<queue>
#include<math.h>
#include<set>
#include<time.h>
#pragma GCC optimize(2)
using namespace std;
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
#define PI acos(-1)
ll a[100005];
int main()
{
    a[1] = a[2] = a[3] = 1;
    for(int i = 4; i <= 100000; i++)
        a[i] = (a[i-1] + a[i-3]) % 998244353;
    int t,n,x,y;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&x,&y);
        if(x == 1 && y == n) cout << a[n] << endl;
        else if(x == 1) cout << a[y-1] << endl;
        else if(y == n) cout << a[n-x] <<endl;
        else if(y == x + 1) printf("0\n");
        else cout << a[(y-1)-(x+1)+1] << endl;
    }
}