【题解】[ARC112E]Cigar Box

· · 题解

注意到只有最后一个操作是有用的, 同时注意到, 最终的序列一定是这样的形式, 可以分成三部分, 左边一部分放是最终操作移动到左边的数, 右边一部分是最终操作移动到右边的数, 中间是从来没有被移动过的数, 并且中间部分是单调递增的.

这时我们可以 \mathcal{O}(n^2) 的枚举左边和右边的个数 L , R , 并且期望快速计算这种情况下移动的方案数.

这相当于我们给 m 个元素上颜色, 颜色为 1\sim L+R , 并且每种颜色都要有, 相当于我们把 m 个球放进 L+R 个无标号的盒子中, 并令盒子的编号为盒子中的序号最大的球的序号, 并给盒子排序, 这样即可一一对应一种移动方案, 同时我们需要钦定这 L+R 个颜色哪些左移哪些右移, 并且我们只需要最后一个操作是我们钦定的方向即可, 之前的颜色相同的可以任意方向, 所以一个局面的移动方案即为

\begin{Bmatrix}m\\L+R\end{Bmatrix}\binom{L+R}{L}2^{m-L-R}

时间复杂度 \mathcal{O}(n^2) .

/************************************************
*Author        :  demonlover
*Created Time  :  2022.09.25.21:15
*Problem       :  ARC112E
************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pii;
template <typename T>
inline bool read(T &x) {
    int f = 1,c = getchar();x = 0;
    while (!isdigit(c)) {if (c == 45)f = -1;c = getchar();}
    while (isdigit(c))x = (x<<3)+(x<<1)+(c^48),c = getchar();
    return x *= f,true;
}
template <typename T,typename... Args>
inline bool read(T &x,Args &...args) {
    return read(x) && read(args...);
}

namespace run {
    const int maxn = 3e3+10;
    const int mod = 998244353;
    int a[maxn],s[maxn][maxn],c[maxn][maxn],bin[maxn];
    int n,m,ans;
    inline bool main() {
        read(n,m);
        for (int i = 1;i <= n;++i)read(a[i]);
        for (int i = 0;i <= m;++i) {
            c[i][0] = 1;s[i][0] = (i == 0);
            for (int j = 1;j <= i;++j)c[i][j] = (c[i-1][j]+c[i-1][j-1])%mod,s[i][j] = (s[i-1][j-1]+1ll*j*s[i-1][j]%mod)%mod;
        }
        for (int i = (bin[0] = 1);i <= m;++i)bin[i] = 1ll*bin[i-1]*2%mod;
        for (int l = 1;l <= n+1;++l)
            for (int r = l-1;r <= n;++r) {
                if (r > l && a[r] < a[r-1])break;
                int L = l-1,R = n-r;
                if (m >= L+R)ans = (ans+1ll*s[m][L+R]*c[L+R][L]%mod*bin[m-(L+R)]%mod)%mod;
            }
        printf("%d\n",ans);
        return 0;
    }
}

int main() {
#ifdef demonlover
    freopen("ARC112E.in","r",stdin);
    freopen("ARC112E.out","w",stdout);
#endif
    return run :: main();
}