Peaks ( Gym 100365H )

这题nk做法还挺正常的。。后面那个循环就很恶心了

考虑 dp[i][j] 表示长度为i的排列，恰好有k个峰的方案数量。

然后转移就是把 i 插入 i-1 的排列。

i显然是i-1的排列里面最大的数，然后插入就只有两种情况：

1. 插入在峰的左右，由于峰不可能相邻，所以可以插入在 2j 个位置
2. 插入在爬山的时候，那么峰的数量+1

$dp[i][j] = 2j\times dp[i-1][j] + ( i - 2(j - 1) )dp[i-1][j-1]$

其实，由于 j 只有 30 ， 可以矩阵快速幂，大概是$k^3( mod + log n )$

但是发现把矩阵写出来可以有这么个神仙结论$f( n , k ) = f( n + 56882 , k ) (\mod 239 )$

暴力暴力

别忘了这题开文件

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
using namespace std;
#define int long long
typedef long long ll;
#define MAXN 57000 
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define inf 0x3f3f3f3f
#define cmx( a , b ) a = max( a , b )
#define cmn( a , b ) a = min( a , b )
#define P 239
void read( signed& x ) {
	scanf("%d",&x);
}
void read( ll& x ) {
	scanf("%lld",&x);
}
int n , k;
int dp[MAXN][31];
signed main() {
	freopen("peaks.in","r",stdin);
	freopen("peaks.out","w",stdout);
	cin >> n >> k;
	n %= 56882;
	dp[0][0] = 1;
	for( int i = 1 ; i <= n ; ++ i ) 
		for( int j = 1 ; j <= k ; ++ j )
			dp[i][j] = ( 2 * j * dp[i - 1][j] % P + ( i - 2 * ( j - 1 ) + P ) % P * dp[i - 1][j - 1] % P ) % P;
	printf("%d\n",dp[n][k]);
}
/*
 * Things you should pay attention to
 * inf is big enough?
 * out of bounds?
 * long long ?
 */