permutation 2
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):
-
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
思路
题目的意思是,给出n,x,y,将n进行排列,并且计算出x为第一个数,y为最后一个数的情况有多少种。如下图所示:
打开提交记录发现有人O(1)过了,于是开始找规律,队友用dfs打了个表。发现有一点规律,如上图红线标记,左边的x+1个数是不变的,右边的n-y+2个数是不变的,那么只需要将中间进行计算就行了。当然,这只是x != 1 且 y != n 的情况,所以需要特判。在想中间怎么算的时候,学长给了一个公式,f(n) = f(n-1) + f(n-3),将所求区间的头尾套进去就能算出得数了。
代码
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 998244353;
typedef long long ll;
#define debug printf("debug\n");
int t,n,x,y;
int f[maxn];
void solve() {
f[1] = f[2] = f[3] = 1;
for(int i=4; i<maxn; i++) {
f[i] = f[i-1] + f[i-3];
f[i] %= mod;
}
}
int main() {
solve();
while(cin >> t) {
while(t--) {
cin >> n >> x >> y;
if(x == 1 && y == n) {
cout << f[n] << endl;
}
else if(x == 1) {
cout << f[y-1] << endl;
}
else if(y == n) {
cout << f[n-x] << endl;
}
else {
cout << f[y-x-1] << endl;
}
}
}
}