C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 544K, 提交时间: 2020-02-14 15:28:41

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ll long long
using namespace std;

const ll mol = 998244353;

ll f[150][150],sum[150][150];
ll l[150],r[150],L[150],R[150];
vector <ll> v;
ll inv[150];

ll add(ll a,ll b) { a += b; if (a >= mol) a -= mol; return a; }
ll sub(ll a,ll b) { a -= b; if (a < 0) a += mol; return a; }
ll qpow(ll a,ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % mol;
		a = a * a % mol;
		b >>= 1;
	}
	return ans;
} 
ll C(ll n,ll m) {
	ll ans = 1;
	for (ll i = n - m + 1; i <= n; i++) ans = ans * (i % mol) % mol;
	return ans * inv[m] % mol;
} 

int main(){ 
	int n;
	scanf("%d" , &n);
	inv[0] = 1;
	for (int i = 1; i <= 50; i++) inv[i] = inv[i - 1] * qpow(i , mol - 2) % mol;
	for (int i = 1; i <= n; i++) { scanf("%lld" , &l[i]); v.push_back(l[i]); } 
	for (int i = 1; i <= n; i++) { scanf("%lld" , &r[i]); v.push_back(r[i] + 1); } 
	sort(all(v));
	v.erase(unique(all(v)) , v.end());
	for (int i = 1; i <= n; i++) { 
		L[i] = lower_bound(all(v) , l[i]) - v.begin() + 1;
		R[i] = lower_bound(all(v) , r[i] + 1) - v.begin();
	} 
	for (int i = 0; i < v.size(); i++) f[0][i] = 1;
	for (int i = 1;i <= n; i++) { 
		for (int j = L[i]; j <= R[i]; j++){ 
			for (int k = i; k >= 1; k--) { 
				if (L[k] > j || R[k] < j) break;
				ll cnt = C(i - k + v[j] - v[j - 1] , i - k + 1);
				f[i][j] = add(f[i][j] , f[k - 1][j - 1] * cnt % mol);
				ll mid = (v[j] + v[j - 1] - 1) % mol;
				sum[i][j] = add(sum[i][j] , add(sum[k - 1][j - 1] * cnt % mol , f[k - 1][j - 1] * cnt % mol * mid % mol * inv[2] % mol * (i - k + 1) % mol));
			} 
		} 
		for (int j = 1; j < v.size(); j++) f[i][j] = add(f[i][j] , f[i][j - 1]),sum[i][j] = add(sum[i][j] , sum[i][j - 1]);
	} 
	printf("%lld\n" , sum[n][v.size() - 1]);
} 

C++(clang++11) 解法, 执行用时: 10ms, 内存消耗: 388K, 提交时间: 2021-02-23 12:57:49

#include <bits/stdc++.h>
#define maxn 105

using namespace std;

const int p = 998244353;

typedef long long ll;

int n;
ll l[maxn], r[maxn];
vector<ll> v;
int f[maxn][maxn], g[maxn][maxn];
int inv[maxn];

int main(){
	scanf("%d", &n);
	inv[1] = 1;for(int i = 2;i <= n;i++) inv[i] = 1ll * (p - p / i) * inv[p % i] % p;
	for(int i = 1;i <= n;i++) scanf("%lld", &l[i]), v.push_back(l[i]);
	for(int i = 1;i <= n;i++) scanf("%lld", &r[i]), v.push_back(++r[i]);
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	for(int i = 1;i <= n;i++){
		l[i] = lower_bound(v.begin(), v.end(), l[i]) - v.begin() + 1;
		r[i] = lower_bound(v.begin(), v.end(), r[i]) - v.begin() + 1;
	}
	int m = v.size();
	for(int i = 0;i < m;i++) f[0][i] = 1;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j < m;j++){
			int C = 1;
			for(int k = 1;i - k >= 0;k++){
				if(!(l[i - k + 1] <= j && j < r[i - k + 1])) break;
				C = 1ll * C * ((v[j] - v[j - 1] + k - 1) % p) % p * inv[k] % p;
				f[i][j] = (f[i][j] + 1ll * f[i - k][j - 1] * C) % p;
				g[i][j] = (g[i][j] + 1ll * g[i - k][j - 1] * C + 1ll * f[i - k][j - 1] * C % p * ((v[j] + v[j - 1] - 1) % p) % p * inv[2] % p * k) % p;
			}
			f[i][j] = (f[i][j] + f[i][j - 1]) % p;
			g[i][j] = (g[i][j] + g[i][j - 1]) % p;
		}
	}
	//int ans = 0;
	//for(int i = 1;i < m;i++) ans = (ans + g[n][i]) % p;
	printf("%d", g[n][m - 1]);
}