Peaks ( Gym 100365H )

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

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

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

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

插入在峰的左右，由于峰不可能相邻，所以可以插入在 2j 个位置
插入在爬山的时候，那么峰的数量+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 ?

 */

巴特西

Peaks Gym 100365H

Peaks ( Gym 100365H )

最新文章

热门文章