提交时间:2024-09-08 15:27:33
运行 ID: 32337
#include<bits/stdc++.h> #define Rf(i,a,b) for(int i=(a);i<=(b);i++) #define Rb(i,a,b) for(int i=(a);i>=(b);i--) #define jp8 push_back #define ll long long #define Rfll(i,a,b) for(ll i=(a);i<=(b);i++) #define PII pair<int,int> #define mpx make_pair using namespace std; const int N=2e5+10; int mod=998244353; int qp(int a,int b){ int x=1; while(b){ if(b&1) x=1ll*a*x%mod; b>>=1;a=1ll*a*a%mod; }return x; } int a[N];int n,m;bool vis[N]; vector<int> e[N],s; int fac[N];int inv[N];int sumfac[N]; int C(int up,int down){ return 1ll*fac[down]*inv[up]%mod*inv[down-up]%mod; }int A(int up,int down){ return 1ll*fac[down]*inv[down-up]%mod; } void slv(){ cin>>n>>m; Rf(i,1,n) e[i].clear();s.clear(); Rf(i,1,n-1) e[i].jp8(i+1); Rf(i,1,n) a[i]=i; int ans=0; Rf(i,1,m){ int x;cin>>x;s.jp8(x); } Rf(i,0,m-1){ Rf(j,i+1,m-1){ e[s[i]].jp8(s[j]); } }Rf(i,1,n) sort(e[i].begin(),e[i].end()); Rf(i,1,n){ Rf(j,i+1,n){ auto now=lower_bound(s.begin(),s.end(),i); int xd=0;int dl=0,dr=0; if(now!=s.end()){ dl=*now; dr=*--upper_bound(s.begin(),s.end(),k); xd=dr-dl-1; if(dl==dr) xd++; }int cntc=i-j+1-xd; Rf(k,0,n-cntc){ int dt=1ll*A(k,n-cntc)*fac[n-k]%mod; ans=(ans+dt)%mod; } } } cout<<ans%mod<<endl; } int main(){ int lim=1010;fac[0]=1;Rf(i,1,lim) fac[i]=1ll*fac[i-1]*i%mod; inv[lim]=qp(fac[lim],mod-2);Rb(i,lim-1,0) inv[i]=1ll*inv[i+1]*(i+1)%mod; int t;cin>>t;while(t--) slv(); return 0; }