C++ 解法, 执行用时: 908ms, 内存消耗: 19208K, 提交时间: 2022-04-30 20:50:08

#include<bits/stdc++.h>
#define VI vector<int>
#define II pair<int,int>
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double db;
const int N=3e5+5;
const int md=998244353;

int n,m,a[N],id[N];
int cnt[N];
ll ans,fac[N*2],inv[N*2],inf[N*2],t[N];
ll Com(int x, int y){
    return fac[x]*inf[y]%md*inf[x-y]%md;
}
void upd(int x, ll y){
    for (; x<=n; x+=x&-x) (t[x]+=y)%=md;
}
ll calc(int x, ll res=0){
    for (; x; x-=x&-x) (res+=t[x])%=md;
    return res;
}
bool cmp(int x, int y){
    return a[x]==a[y]? (x>y):(a[x]>a[y]);
}
void solve(){
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; ++i) {
        id[i]=i;
        scanf("%d",&a[i]);
    }
    sort(id+1,id+n+1,cmp);
    ll ans=0;
    for (int i=1; i<=n; ++i){
        (ans+=Com(n-id[i]+m,m)*calc(id[i])%md)%=md;
        upd(id[i],Com(id[i]+m-1,m));
    }
    for (int i=1; i<=n; ++i) t[i]=0;
    printf("%lld\n",ans);
}
void init(){
    fac[0]=fac[1]=inv[1]=inv[0]=inf[0]=inf[1]=1;
    for (int i=2; i<=600000; ++i){
        fac[i]=fac[i-1]*i%md;
        inv[i]=(md-md/i)*inv[md%i]%md;
        inf[i]=inf[i-1]*inv[i]%md;
    }
}
int main(){
    int T=1;
    init();
    scanf("%d",&T);
    while (T--){
        solve();
    }
}