【ABC242EX】Random Painting

【ABC242EX】Random Painting

by AmanoKumiko

Description

有\(n\)个位置，\(m\)个区间

每次会随机选出一个区间，并把区间的位置变成黑色（初始都为白色）

求把所有位置变成黑色的期望次数对\(998244353\)取模的结果

Input

第一行读入\(n,m\)

然后\(m\)行读入区间

Output

一行一个数表示答案

Sample Input

3 3
1 1
1 2
2 3

Sample Output

499122180

Data Constraint

\(1\le N,M\le 400\)

Solution

第一次用\(min-max\)反演

令\(max\)表示期望把整个集合染黑的次数

\(min\)表示期望第一次染黑集合中任意位置的次数

那么接下来要做的就是设个\(dp\)

令\(f_{i,j}\)表示集合最后一次选了位置\(i\)，和集合有交的区间数为\(j\)的容斥系数

枚举上一次选的位置和有交区间数，令其为\(f_{x,y}\)

可以发现，我们的新区间数就是\(y\)减去\(x\)和\(i\)都有交的，加上只和\(i\)有交的

因为在\(i\)之前选的和\(x\)有交的区间也一定会在上面算到

再根据——从\(i\)个元素中选出\(j\)个元素中的任意一个元素的期望次数为\(\frac{i}{j}\)就行了

Code

#include
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mo 998244353
#define N 410

int n,m;
LL f[N][N],a[N][N],b[N],ans;
struct node{int l,r;}p[N];

bool cmp(node x,node y){return x.l