problem

將正整數 $1～n$ 任意劃分成 $m$ 個非空集合 $A_1,...,A_m$。

一個劃分是守序的，當且僅當存在一個環排列 $(p_1,...,p_m)$，使得 $\max A_{p_i}>\min A_{p_{i?1}}$。$p_0=p_m$。

兩個劃分本質不同，當且僅當存在兩個數在一個劃分中屬于同一個集合，而在另一個劃分成屬于不同集合。

求本質不同的守序劃分方案數，對 998244353 取模。

$n,m\le 500$。

solution

守序的判定可以轉化為：不存在一個 $i$，使得 $1～i$ 各自隸屬集合的集合 $S?$ $i+1～n$ 各自隸屬集合的集合 $T=?$。

簡單證明一下：不管圓排列是怎樣的，$T$ 里面的集合最小值最大值都是 $\ge i+1$，而 $S$ 里面的集合最小值最大值都是 $\le i$ 的，而圓排列至少會讓一個屬于 $S$ 的集合在一個屬于 $T$ 的集合后一個位置，那么這個時候一定無法滿足條件。

設 $f(i,j,k):$ 考慮前 $i$ 個數，一共劃分成了 $j$ 個集合，其中有 $k$ 個集合還未封閉。區間封閉代表這已經生成了一個集合，之后不會再加數了。

則除了 $i=n$ 時，其余時候是不能 $k=0$ 的。考慮轉移到 $f(i,j,k)$ 的幾種情況。

• 新增一個封閉區間。$f(i?1,j?1,k)$。
• 新增一個未封閉區間。$f(i?1,j?1,k?1)$。
• 隨便加入一個未封閉區間后仍處于未封閉狀態。$f(i?1,j,k)\times k$。
• 隨便加入一個未封閉區間后使之封閉。$f(i?1,j,k+1)\times (k+1)$。

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; }

總結

以上是生活随笔為你收集整理的守列划分问题（圆排列+排列dp+结论）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。