2020-2021:teams:legal_string:jxm2001:contest:arc_112
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:arc_112 [2021/02/28 10:16] 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 ===== |
| ==== 题意 ==== | ==== 题意 ==== | ||
| 行 39: | 行 39: | ||
| <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.1614478605.txt.gz · 最后更改: 2021/02/28 10:16 由 jxm2001
