2020-2021:teams:legal_string:组队训练比赛记录:contest2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest2 [2021/07/13 13:58] lgwza [题解] |
2020-2021:teams:legal_string:组队训练比赛记录:contest2 [2021/07/18 11:04] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 94: | 行 94: | ||
| _rep(i,1,n) | _rep(i,1,n) | ||
| enter((ss-s[i]+mod)%mod); | 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; | return 0; | ||
| } | } | ||
| 行 197: | 行 131: | ||
| - 高斯消元法求 $A^{-1}$ 和 $|A|$，记 $A^{-1}=C=(c_{ij})$，复杂度 $O(n^3)$。 | - 高斯消元法求 $A^{-1}$ 和 $|A|$，记 $A^{-1}=C=(c_{ij})$，复杂度 $O(n^3)$。 | ||
| - 执行修改操作，将 $(x,y)$ 元修改为 $z$，改变量记为 $delta=z-a_{xy}$，改变后的矩阵记为 $A'=(a'_{ij})$。 | - 执行修改操作，将 $(x,y)$ 元修改为 $z$，改变量记为 $delta=z-a_{xy}$，改变后的矩阵记为 $A'=(a'_{ij})$。 | ||
| - | - 计算修改后的行列式的值 $|A'|$，用定理 5 对第 $x$ 行按行展开来求，而由定理 4，$A'_{ij}=A_{ij}=|A|c_{jx}$，故 $\displaystyle |A'|=\sum_{j=1}^na'_{xj}|A|c_{ji}$。 | + | - 计算修改后的行列式的值 $|A'|$，用定理 5 对第 $x$ 行按行展开来求，而由定理 4，$A'_{ij}=A_{ij}=|A|c_{ji}$，故 $\displaystyle |A'|=\sum_{j=1}^na'_{xj}|A|c_{jx}$。 |
| - 令 $|A|=|A'|$，并用定理 1 计算 $(A')^{-1}$：令 $u=(0,\cdots,0,1,0,\cdots,0)^T$（第 $x$ 个分量为 1，其它分量为 0 的列向量），$v=(0,\cdots,0,delta,0,\cdots,0)^T$ （第 $y$ 个分量为 $delta$，其它分量为 0 的列向量），即可在 $O(n^2)$ 内算出 $(A')^{-1}=(A+uv^T)=A^{-1}-\dfrac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$。然后令 $C=A^{-1}=(A')^{-1},A=A'$。回到步骤 2，进行下一步修改操作，直至修改操作结束。 | - 令 $|A|=|A'|$，并用定理 1 计算 $(A')^{-1}$：令 $u=(0,\cdots,0,1,0,\cdots,0)^T$（第 $x$ 个分量为 1，其它分量为 0 的列向量），$v=(0,\cdots,0,delta,0,\cdots,0)^T$ （第 $y$ 个分量为 $delta$，其它分量为 0 的列向量），即可在 $O(n^2)$ 内算出 $(A')^{-1}=(A+uv^T)=A^{-1}-\dfrac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$。然后令 $C=A^{-1}=(A')^{-1},A=A'$。回到步骤 2，进行下一步修改操作，直至修改操作结束。 | ||
| 行 293: | 行 227: | ||
| </code> | </code> | ||
| </hidden> | </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> | ||
| + | |||
| ====== 赛后总结 ====== | ====== 赛后总结 ====== | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest2.1626155924.txt.gz · 最后更改: 2021/07/13 13:58 由 lgwza
