A40228. 排列数
填空题
困难
知识点
题目描述
排列数
题目描述
在一个排列中，一个折点是指排列中的一个元素，它同时小于两边的元素，或者同时大于两边的元素。
对于一个 1∼n 的排列，如果可以将这个排列中包含 t 个折点，则它称为一个 t+1 单调序列。
例如，排列 (1,4,2,3) 是一个 3 单调序列，其中 4 和 2 都是折点。
给定 n 和 k，请问 1∼n 的所有排列中有多少个 k 单调队列？
输入格式
输入一行包含两个整数 n,k。
输出格式
输出一个整数，表示答案。
答案可能很大，你可需要输出满足条件的排列数量除以 123456 的余数即可。
数据范围
1≤k≤n≤500
输入样例：
4 2
输出样例：
12
参考答案
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {
template <typename T> inline void read(T &x) {
x = 0; T f = 1;char s = getchar();
for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;
for(; isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);
x *= f;
}
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define _srep(n,m,i)for (register int i = (n); i >= (m); i--)
#define _sfor(n,m,i)for (register int i = (n); i > (m); i--)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
const int Mod = 123456;
const int N = 5e2+5;
int dp[N][N] ;
int main() {
int n, k; read(n); read(k);
dp[1][0] = 1;
for(int i = 2; i <= n; ++i) {
dp[i][0] = 2;
for(int j = 0; j <= i - 2; ++j) {
dp[i][j] %= Mod;
dp[i+1][j] += dp[i][j] * (j+1);
dp[i+1][j+1] += dp[i][j] * 2;
dp[i+1][j+2] += dp[i][j] * (i-j-2);
}
}
cout << dp[n][k-1] % Mod << endl;
}答案解析
答案就是d p [ n ] [ k − 1 ] dp[n][k-1]dp[n][k−1]
上一题
下一题