题解：P11616 瓦解

可爱大黄兔 · 2025-01-26 09:14:46 · 题解

我们可以先求出满足 a_i>a_i-1 的个数 cnt，然后答案就可以转化为依次求出在 (n-cnt) 个数内选出 (i-cnt) 个数的方案数。根据组合数学可以求出答案为 \sum_{i=cnt}^n C_{n-cnt}^{i-cnt}。

#include<bits/stdc++.h>
// 7 10
// 9 23
// 1 6 7 8 9 20
typedef long long ll;
using namespace std;
int T;
int n,m;
ll a[10000010];
ll fac[10000010];
ll inv[10000010];
ll finv[10000010];
const ll mod=998244353;
ll fastpow(ll a, ll b) {
    ll ans = 1, base = a;
    while (b != 0) {
        if (b & 1)
            ans = (ans * base % mod) % mod;
        base = (base * base) % mod;
        b >>= 1;
    }
    ans %= mod;
    return ans;
}

ll C(ll n,ll m){
    if(m<0||m>n)return 0;
    return fac[n]*finv[n-m]%mod*finv[m]%mod;
}
int main(){
    inv[1]=1;
    for(int i=2;i<=10000000;i++)inv[i]=((mod-mod/i)*inv[mod%i])%mod;
    fac[0]=finv[0]=1;
    for(int i=1;i<=10000000;i++)fac[i]=fac[i-1]*i%mod,finv[i]=finv[i-1]*inv[i]%mod;
    cin>>T;
    while(T--){
        ll cnt=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            if(a[i]<=a[i-1]){
                cnt++;
            }
        }
        cnt++;
//      if(m<cnt){
//          puts("0");
//          continue;
//      }
//      puts("Run");
        ll ans=0;
        for(int i=cnt;i<=m;i++){
            ans+=C(n-cnt,i-cnt);
            ans%=mod;
        }
        cout<<ans%mod<<endl;

    }
}