多校冲刺 NOIP 20211111 模拟 (28)

T1

\(f_{i,j}\)表示剩下i瓜子，j瓜子壳的期望步数

逆推转移即可

T2

发现k很小，考虑倒序枚举i，链表维护大于i的数

然后暴力跳左边和右边k个大于i的数即可

代码

T1

#include 
using namespace std;
#define int long long
const int N = 4e3 + 11;
const int mod = 998244353;
int n;
int inv[N];
int jc[N], ny[N];
int f[N / 2][N];
inline void md(int& x) {
    if (x >= mod)
        x -= mod;
    return;
}
int fm(int x, int y) {
    int ans = 1;
    for (; y; y >>= 1, x = x * x % mod)
        if (y & 1)
            ans = ans * x % mod;
    return ans;
}
void pre() {
    jc[0] = ny[0] = 1;
    inv[0] = inv[1] = 1;
    for (int i = 1; i <= 4e3; ++i) jc[i] = jc[i - 1] * i % mod;
    ny[(int)4e3] = fm(jc[(int)4e3], mod - 2);
    for (int i = 4e3 - 1; i; --i) ny[i] = ny[i + 1] * (i + 1) % mod, inv[i + 1] = jc[i] * ny[i + 1] % mod;
    return;
}
signed main() {
    FILE* x = freopen("eat.in", "r", stdin);
    x = freopen("eat.out", "w", stdout);
    //	for(int i=1;i<=100;++i)for(int j=1;j<=100;++j) if(i*fm(j,mod-2)%mod==332748119) cout<> n;
    for (int ed, i = 1; i <= n; ++i) {
        ed = 2 * (n - i);
        md(f[i][0] += (1 + f[i - 1][2]) % mod);
        for (int j = 1; j <= ed; ++j) {
            md(f[i][j] += j * (1 + f[i][j - 1]) % mod * inv[i + j] % mod);
            md(f[i][j] += i * (f[i - 1][j + 2] + 1) % mod * inv[i + j] % mod);
        }
    }
    cout << f[n][0] << endl;
    return 0;
}

T2

#include 
#include 
using namespace std;
const int N = 5e5 + 11;
int n, k;
int a[N], rle[N];
int top, sta[N];
int suml[52], numl, sumr[52], numr;
int rnxt[N], lnxt[N];
int l[N], r[N];
long long ans;
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s;
}
void add(int i) {
    int loc = rle[i];
    l[loc] = lnxt[i], r[loc] = rnxt[i];
    r[l[loc]] = loc, l[r[loc]] = loc;
    return;
}
void js(int x) {
    int val = 0;
    numl = numr = 0;
    memset(suml, 0, sizeof(suml));
    memset(sumr, 0, sizeof(sumr));
    add(x);
    for (int sl = 1, i = rle[x]; i && sl <= k; i = l[i], ++sl) suml[++numl] = i - l[i];
    for (int sl = 1, i = rle[x]; i && sl <= k; i = r[i], ++sl) sumr[++numr] = (r[i] ? r[i] : n + 1) - i;
    for (int wz, i = 1; i <= numl; ++i) {
        wz = k - i + 1;
        if (wz > numr)
            continue;
        ans += 1ll * suml[i] * sumr[wz] * x;
    }
    return;
}
int main() {
    FILE* x = freopen("kth.in", "r", stdin);
    x = freopen("kth.out", "w", stdout);
    n = read();
    k = read();
    for (int i = 1; i <= n; ++i) {
        rle[a[i] = read()] = i;
        while (top && a[sta[top]] < a[i]) --top;
        lnxt[a[i]] = sta[top];
        sta[++top] = i;
    }
    top = 0;
    for (int i = n; i; --i) {
        while (top && a[sta[top]] < a[i]) --top;
        rnxt[a[i]] = sta[top];
        sta[++top] = i;
    }
    for (int loc, i = n; i > n - k + 1; --i) add(i);
    for (int i = n - k + 1; i; --i) js(i);
    cout << ans << endl;
    return 0;
}