HDU 6630 [2019 Multi-University Training Contest 5]

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):

  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

思路

题目的意思是,给出n,x,y,将n进行排列,并且计算出x为第一个数,y为最后一个数的情况有多少种。如下图所示:
HDU 6630 [2019 Multi-University Training Contest 5]
打开提交记录发现有人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;
			}
		}
	}
}

题目来源

HDU 6630 permutation 2

上一篇:HDU-多校2-Everything Is Generated In Equal Probability(公式+逆元)


下一篇:STL初探