题目地址: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;
}