2020-2021:teams:legal_string:jxm2001:contest:arc_112
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:arc_112 [2021/02/28 09:54] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:contest:arc_112 [2021/02/28 10:30] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== Atcoder Rugular Contest 113 ====== | + | ====== Atcoder Rugular Contest 112 ====== |
| - | [[https://atcoder.jp/contests/arc113|比赛链接]] | + | [[https://atcoder.jp/contests/arc112|比赛链接]] |
| - | ===== F - Social Distance ===== | + | ===== E - Cigar Box ===== |
| ==== 题意 ==== | ==== 题意 ==== | ||
| 行 28: | 行 28: | ||
| 于是剩下的排列就是 $(a_{l+1},a_{l+2}\cdots a_{n-r})$，所以只要 $a_{l+1},a_{l+2}\cdots a_{n-r}$ 单增即可计入贡献。 | 于是剩下的排列就是 $(a_{l+1},a_{l+2}\cdots a_{n-r})$，所以只要 $a_{l+1},a_{l+2}\cdots a_{n-r}$ 单增即可计入贡献。 | ||
| + | |||
| + | 最后问题就剩下计算每个 $\prod_{i=1}^{l+r}(2i)^{c_i}$ 了，设 $\text{dp}(i,j)=\prod_{k=1}^{i}(2k)^{c_k}\left(\sum_{k=1}^{i}{c_k}=j\right)$，考虑枚举 $c_i$，于是有状态转移： | ||
| + | |||
| + | $$ | ||
| + | \text{dp}(i,j)=\sum_{k=0}^j (2i)^{j-k}\text{dp}(i-1,k) | ||
| + | $$ | ||
| + | |||
| + | 记录一下前缀和，即可 $O(nm)$ 完成 $\text{dp}$，最后 $O(n^2)$ 枚举 $l,r$ 统计贡献即可。 | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| + | const int MAXN=3005,Mod=998244353; | ||
| + | int C[MAXN][MAXN],dp[MAXN][MAXN],a[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(); | ||
| + | _rep(i,1,n)a[i]=read_int(); | ||
| + | C[0][0]=1; | ||
| + | _rep(i,1,n){ | ||
| + | C[i][0]=1; | ||
| + | _rep(j,1,i) | ||
| + | C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod; | ||
| + | } | ||
| + | dp[0][0]=1; | ||
| + | _rep(i,1,n){ | ||
| + | int s=0; | ||
| + | _rep(j,0,m){ | ||
| + | s=(2LL*i*s+dp[i-1][j])%Mod; | ||
| + | dp[i][j]=s; | ||
| + | } | ||
| + | } | ||
| + | int ans=0; | ||
| + | _rep(i,0,n){ | ||
| + | for(int j=n-i;j>=0;j--){ | ||
| + | if(n-i-j>=2&&a[n-j]<a[n-j-1])break; | ||
| + | if(m-i-j>=0)ans=(ans+1LL*dp[i+j][m-i-j]*C[i+j][i])%Mod; | ||
| + | } | ||
| + | } | ||
| + | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/arc_112.1614477241.txt.gz · 最后更改: 2021/02/28 09:54 由 jxm2001
