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

我不是女神ヾ 2021-11-05 06:44 238阅读 0赞

题目链接：[传送门][Link 1]

### 题意： ###

T组测试样例，每组测试样例输入N，X，Y，N代表一个数组的长度，X代表数组的第一个数，Y代表数组的最后一个数，问排列1~N有多少种可能，并且满足 ![\\left | P\_\{i\}-P\_\{i+1\} \\right |\\leqslant 2][left _ P_i_-P_i_1_ _right _leqslant 2]，（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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy_size_16_color_FFFFFF_t_70][]

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy_size_16_color_FFFFFF_t_70 1][]

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy_size_16_color_FFFFFF_t_70 2][]

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy_size_16_color_FFFFFF_t_70 3][]

观察此时分两种情况，若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;
        }
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6630
[left _ P_i_-P_i_1_ _right _leqslant 2]: https://private.codecogs.com/gif.latex?%5Cleft%20%7C%20P_%7Bi%7D-P_%7Bi&plus;1%7D%20%5Cright%20%7C%5Cleqslant%202
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy_size_16_color_FFFFFF_t_70]: /images/20211104/ab5c0933063d48ae8875ebeeb70d67cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy_size_16_color_FFFFFF_t_70 1]: /images/20211104/3f6f7ba9d8964058ad4b6388decd1564.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy_size_16_color_FFFFFF_t_70 2]: /images/20211104/e22f36d74f9342aa8c5a69c48275c4f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy_size_16_color_FFFFFF_t_70 3]: /images/20211104/36245bc431234c6ca05698b812840419.png