题解：P11616 瓦解

chenly8128 · 2025-01-26 11:36:36 · 题解

题解

最多分成 m 段非空连续段，等价于选择 m-1 个不重合的分割点。

为了满足严格单调的条件，递减（或相等）的连续两个数之间必须要有一个分割点。因此只有剩下的分割点可以在剩下的间隔中任意选择。设必须要有的分割点有 cnt 个。则总的可能数为 ans = \sum_{i=0}^{m-1-cnt} C_{n-1-cnt}^{i}。组合数可以递推累加。复杂度为 O(\sum_{}n)。

代码

// Author: chenly8128
// Created: 2025-01-25 13:49:52

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
inline int read(void) {
    int res = 0;bool flag = true;char c = getchar();
    while (c < '0' || c > '9') {flag ^= (c == '-');c = getchar();}
    while (c >= '0' && c <= '9') {res = (res << 3) + (res << 1) + (c ^ 48);c = getchar();}
    return flag ? res : -res;
}
long long qpow (long long x,int k) {
    long long ans = 1;
    while (k) {
        if (k&1) ans = ans * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return ans;
}
int main (void) {
    int T = read();
    while (T--) {
        int n = read();int m = read()-1,x,last = -0x3f3f3f3f;
        int cnt = 0;
        for (int i = 1;i <= n;i++) {
            x = read();
            if (x <= last) cnt++;
            last = x;
        }
        if (cnt > m) {
            printf ("0\n");
            continue;
        }
        long long ans = 1,now = 1;
        for (int i = 1;i <= m-cnt;i++) {
            now = now * (n-cnt-i) % mod * qpow(i,mod-2) % mod;
            ans += now;
        }
        printf ("%d\n",ans % mod);
    }
    return 0;
}