孝感建设局网站,唐山网站主页制作,南通关键词优化软件,网站发展规划problem
将正整数 1∼n1\sim n1∼n 任意划分成 mmm 个非空集合 A1,...,AmA_1,...,A_mA1,...,Am。
一个划分是守序的#xff0c;当且仅当存在一个环排列 (p1,...,pm)(p_1,...,p_m)(p1,...,pm)#xff0c;使得 maxApiminApi−1\max A_{p_i}\min A_{p_{i-…problem
将正整数 1∼n1\sim n1∼n 任意划分成 mmm 个非空集合 A1,...,AmA_1,...,A_mA1,...,Am。
一个划分是守序的当且仅当存在一个环排列 (p1,...,pm)(p_1,...,p_m)(p1,...,pm)使得 maxApiminApi−1\max A_{p_i}\min A_{p_{i-1}}maxApiminApi−1。p0pmp_0p_mp0pm。
两个划分本质不同当且仅当存在两个数在一个划分中属于同一个集合而在另一个划分成属于不同集合。
求本质不同的守序划分方案数对 998244353 取模。
n,m≤500n,m\le 500n,m≤500。
solution
守序的判定可以转化为不存在一个 iii使得 1∼i1\sim i1∼i 各自隶属集合的集合 S⋂S\bigcapS⋂ i1∼ni1\sim ni1∼n 各自隶属集合的集合 T∅T\emptyT∅。 简单证明一下不管圆排列是怎样的TTT 里面的集合最小值最大值都是 ≥i1\ge i1≥i1而 SSS 里面的集合最小值最大值都是 ≤i\le i≤i 的而圆排列至少会让一个属于 SSS 的集合在一个属于 TTT 的集合后一个位置那么这个时候一定无法满足条件。 设 f(i,j,k):f(i,j,k):f(i,j,k): 考虑前 iii 个数一共划分成了 jjj 个集合其中有 kkk 个集合还未封闭。区间封闭代表这已经生成了一个集合之后不会再加数了。
则除了 ininin 时其余时候是不能 k0k0k0 的。考虑转移到 f(i,j,k)f(i,j,k)f(i,j,k) 的几种情况。
新增一个封闭区间。f(i−1,j−1,k)f(i-1,j-1,k)f(i−1,j−1,k)。新增一个未封闭区间。f(i−1,j−1,k−1)f(i-1,j-1,k-1)f(i−1,j−1,k−1)。随便加入一个未封闭区间后仍处于未封闭状态。f(i−1,j,k)×kf(i-1,j,k)\times kf(i−1,j,k)×k。随便加入一个未封闭区间后使之封闭。f(i−1,j,k1)×(k1)f(i-1,j,k1)\times (k1)f(i−1,j,k1)×(k1)。
code
#include bits/stdc.h
using namespace std;
#define mod 998244353
#define maxn 505
int dp[maxn][maxn][maxn];
int n, m;signed main() {scanf( %d %d, n, m );dp[0][0][0] 1;for( int i 1;i n;i )for( int j 1;j m;j )for( int k ( i ! n );k j;k ) //在n之前是不能让集合出现全都封闭的情况dp[i][j][k] ( 1ll * dp[i - 1][j - 1][k] 1ll * dp[i - 1][j - 1][max( 0, k - 1 )] 1ll * dp[i - 1][j][k 1] * ( k 1 ) 1ll * dp[i - 1][j][k] * k ) % mod;//新开一个封闭集合 / 自己单独为一个集合//新开一个不封闭的集合等待后续的加入//随便加入一个不封闭的集合使之封闭//随便加入一个不封闭的集合等待后续加入printf( %d\n, dp[n][m][0] );return 0;
}
