差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest2 [2021/07/13 13:59]
lgwza [题解]
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest2 [2021/07/18 11:04] (当前版本)
jxm2001
@@ 行 94: / 行 94: @@
 	_rep(i,1,n)
 	enter((ss-s[i]+mod)%mod);
-	return 0;
-}
-</code>
-</hidden>
-===== E. 上升下降子序列 =====
-==== 题意 ====
-问有多少个 $1\sim n$ 的排列可以拆分成一个上升子序列和一个下降子序列。
-==== 题解 ====
-如果一个排列存在多种拆分，则仅考虑上升序列最长的拆分。
-如果存在多个最长的上升子序列，则考虑所有最长上升子序列 $(a_1,a_2\cdots a_m)$ 中 $a_m$ 最大的子序列，如果还有相同的则依次比较 $a_{m-1},a_{m-2}\cdots$
-易知，这样任意一个满足条件的排列与拆分一一对应。
-设 $\text{dp}(i,j,k,t)$ 表示 $1\sim i$ 的排列满足上升子序列最后一个元素下标为 $j$ 且下降子序列的第一个元素下标为 $k$，且 $t=0/1$ 表示能否将上升序列最后一个元素加入下降序列的方案数。
-如果 $k=i+1$ 则表示下降序列为空。枚举新加入 $i+1$ 的位置 $p$，设原序列为 $s[1\sim i]$，则新序列为 $s[1\sim p-1],i+1,s[p\sim i]$。
-同时加入 $i+1$ 时需要维护上升序列最长且逆向字典序最大的性质。
-  - 如果 $p\ge j$，显然应该将 $i+1$ 加入上升序列末尾。
-  - 如果 $p=j$，则显然原先上升序列的最后一个元素 $s_j$ 被 $i+1$ 替换，于是需要考虑能否将 $s_j$ 加入下降序列。
-  - 如果 $p\lt j$，则只能将 $i+1$ 加入下降序列开头，此时需要满足 $p\le k$。
-上述转移的正确性由 $1\sim i+1$ 的排列对应的上升序列最长且逆向字典序最大的拆分一定来自唯一的 $1\sim i$ 的排列对应的上升序列最长且逆向字典序最大的拆分再加上 $i+1$ 这条性质保证，但本人不会证明。
-<hidden 查看代码>
-<code cpp>
-const int MAXN=105;
-int dp[MAXN][MAXN][MAXN][2],mod;
-void add(int &x,int y){
-	x+=y;
-	if(x>=mod)x-=mod;
-}
-int main()
-{
-	int n=read_int();
-	mod=read_int();
-	dp[1][1][2][1]=1;
-	_for(i,1,n)_rep(j,1,i)_rep(k,1,j+1)_for(t,0,2){
-		_rep(p,1,i+1){
-			if(p>j)
-			add(dp[i+1][p][k<p?k:(k+1)][k>=p],dp[i][j][k][t]);
-			else if(p==j){
-				if(t){
-					if(j<k)
-					add(dp[i+1][p][j+1][1],dp[i][j][k][t]);
-					else
-					add(dp[i+1][p][k][0],dp[i][j][k][t]);
-				}
-			}
-			else{
-				if(p<=k)
-				add(dp[i+1][j+1][p][j<k?1:t],dp[i][j][k][t]);
-			}
-		}
-	}
-	int ans=0;
-	_rep(i,1,n)_rep(j,1,n+1)_for(k,0,2)
-	add(ans,dp[n][i][j][k]);
-	enter(ans);
 	return 0;
 }
@@ 行 293: / 行 227: @@
 </code>
 </hidden>
+===== E. 上升下降子序列 =====
+==== 题意 ====
+问有多少个 $1\sim n$ 的排列可以拆分成一个上升子序列和一个下降子序列。
+==== 题解 ====
+如果一个排列存在多种拆分，则仅考虑上升序列最长的拆分。
+如果存在多个最长的上升子序列，则考虑所有最长上升子序列 $(a_1,a_2\cdots a_m)$ 中 $a_m$ 最大的子序列，如果还有相同的则依次比较 $a_{m-1},a_{m-2}\cdots$
+易知，这样任意一个满足条件的排列与拆分一一对应。
+设 $\text{dp}(i,j,k,t)$ 表示 $1\sim i$ 的排列满足上升子序列最后一个元素下标为 $j$ 且下降子序列的第一个元素下标为 $k$，且 $t=0/1$ 表示能否将上升序列最后一个元素加入下降序列的方案数。
+如果 $k=i+1$ 则表示下降序列为空。枚举新加入 $i+1$ 的位置 $p$，设原序列为 $s[1\sim i]$，则新序列为 $s[1\sim p-1],i+1,s[p\sim i]$。
+同时加入 $i+1$ 时需要维护上升序列最长且逆向字典序最大的性质。
+  - 如果 $p\ge j$，显然应该将 $i+1$ 加入上升序列末尾。
+  - 如果 $p=j$，则显然原先上升序列的最后一个元素 $s_j$ 被 $i+1$ 替换，于是需要考虑能否将 $s_j$ 加入下降序列。
+  - 如果 $p\lt j$，则只能将 $i+1$ 加入下降序列开头，此时需要满足 $p\le k$。
+上述转移的正确性由 $1\sim i+1$ 的排列对应的上升序列最长且逆向字典序最大的拆分一定来自唯一的 $1\sim i$ 的排列对应的上升序列最长且逆向字典序最大的拆分再加上 $i+1$ 这条性质保证，但本人不会证明。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=105;
+int dp[MAXN][MAXN][MAXN][2],mod;
+void add(int &x,int y){
+	x+=y;
+	if(x>=mod)x-=mod;
+}
+int main()
+{
+	int n=read_int();
+	mod=read_int();
+	dp[1][1][2][1]=1;
+	_for(i,1,n)_rep(j,1,i)_rep(k,1,j+1)_for(t,0,2){
+		_rep(p,1,i+1){
+			if(p>j)
+			add(dp[i+1][p][k<p?k:(k+1)][k>=p],dp[i][j][k][t]);
+			else if(p==j){
+				if(t){
+					if(j<k)
+					add(dp[i+1][p][j+1][1],dp[i][j][k][t]);
+					else
+					add(dp[i+1][p][k][0],dp[i][j][k][t]);
+				}
+			}
+			else{
+				if(p<=k)
+				add(dp[i+1][j+1][p][j<k?1:t],dp[i][j][k][t]);
+			}
+		}
+	}
+	int ans=0;
+	_rep(i,1,n)_rep(j,1,n+1)_for(k,0,2)
+	add(ans,dp[n][i][j][k]);
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
 ====== 赛后总结 ======

CVBB ACM Team

用户工具

站点工具

差别

页面工具