题解 | 小A的线段（easy version）

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10,P=998244353;

int n,m,res;
vector<pair<int,int>> v;
vector<int> cf(N+10,0);

bool pan_cf(){
	int sum=0;
	for(int i=1;i<=n;i++){
		sum=sum+cf[i];
		if(sum<2) return false;
	}
	return true;
}

void dfs(int i){
	
	if(i==m){
		if(pan_cf()){
			res=(res+1)%P;
		}
		return;
	}
	
	cf[v[i].first]++;
	cf[v[i].second+1]--;
	dfs(i+1);
	cf[v[i].first]--;
	cf[v[i].second+1]++;
	dfs(i+1);
	return;
}

void solve(){
	
	dfs(0);
	
	cout<<res<<endl;
	
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	int start,end;
	for(int i=1;i<=m;i++){
		cin>>start>>end;
		v.push_back({start,end});
	}
	
	solve();
    return 0;
}