C++(g++ 7.5.0) 解法, 执行用时: 248ms, 内存消耗: 1712K, 提交时间: 2023-03-23 13:19:38

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const ll P = 998244353;
const int maxn = 410;
int sz[maxn][maxn], dp[maxn][maxn];


ll qpow(ll a, ll k = P-2){
	ll ans = 1;
	while(k){
		if(k&1) ans = ans * a % P;
		a = a * a % P, k >>= 1;
	}
	return ans;
}

void solve(){
	int n, m; cin >> n >> m;
	vector<pair<int, int>>interval(m);
	for(auto &[L, R]: interval) cin >> L >> R;

	for(int l = 0 ; l <= n ; l ++){
		for(int r = l+1 ; r <= n ; r ++){
			for(auto &[L, R]: interval){
				if(L>l and L<=r and R>=r) sz[l][r] ++;
			}
		}
	}

	dp[0][0] = -1;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			for(int pre = 0 ; pre < i ; pre ++){
				if(sz[pre][i]>j) continue;
				dp[i][j] = (dp[i][j] - dp[pre][j-sz[pre][i]]) % P;
			}
		}
	}

	ll ans = 0;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			ans = (ans + dp[i][j] * qpow(j) % P * m) % P;
		}
	}
	cout << (ans+P)%P << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	solve();

	return 0;
}