General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
86496813 Practice:
JKLover
1295F - 8 C++17 (GCC 7-32) Accepted 46 ms 3712 KB 2020-07-11 14:05:21 2020-07-11 14:05:21
→ Source
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 998244353;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
int fpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
const int N = 100 + 10;
int n, l[N], r[N], dp[N][N], pos[N], tot = 0, prod = 1, fac[N], invfac[N];
// [pos(i), pos(i + 1) - 1)
int main()
{
	n = read(), fac[0] = 1;
	for (int i = 1; i <= n; ++i)
	{
		fac[i] = mul(fac[i - 1], i);
		pos[++tot] = l[n + 1 - i] = read();
		pos[++tot] = (r[n + 1 - i] = read()) + 1;
		prod = mul(prod, pos[tot] - pos[tot - 1]);
	}
	invfac[n] = fpow(fac[n], P - 2);
	for (int i = n - 1; i >= 0; --i)
		invfac[i] = mul(invfac[i + 1], i + 1);
	sort(pos + 1, pos + 1 + tot);
	tot = unique(pos + 1, pos + 1 + tot) - pos - 1;
	for (int j = 0; j <= tot; ++j)
		dp[0][j] = 1;
	for (int i = 1; i <= n; ++i)
	{
		int L = lower_bound(pos + 1, pos + 1 + tot, l[i]) - pos;
		int R = upper_bound(pos + 1, pos + 1 + tot, r[i]) - pos - 1;
		l[i] = L, r[i] = R;
		for (int j = 1; j < tot; ++j)
		{
			dp[i][j] = dp[i][j - 1];
			if (L <= j && j <= R)
			{
				int len = pos[j + 1] - pos[j] - 1, coef = 1;
				for (int k = 1; k <= i; ++k)
				{
					if (j < l[i - k + 1] || j > r[i - k + 1])
						break;
					coef = mul(coef, len + k);
					inc(dp[i][j], mul(dp[i - k][j - 1], mul(coef, invfac[k])));
				}
			}
		}
	}
	int ans = mul(dp[n][tot - 1], fpow(prod, P - 2));
	cout << ans << '\n';
	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details