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

#include <iostream>
#include <istream>
#include <ratio>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
// 算法不复杂，但是测试过程很长，一直有不通过的
// 主要的原因是，自己写的求交集，并集的函数有很多小问题
// 一定要测试自定义函数，确保正确，不然这种题查错非常难受
struct Line {
    int s;
    int e;
};

istream& operator>> (istream& in, Line& v) {
    return in >> v.s >> v.e;
}

// 交集
Line* Intersection(const Line& l, const Line& r) {
    auto s = max(l.s, r.s);
    auto e = min(l.e, r.e);
    if(s > e) {
        return nullptr;
    } else {
        return new Line{s,e};
    }
}
unordered_map<int,unordered_map<int,Line*>> gInter;
Line* GetInter(int i, int j) {
    if(i > j) {
        swap(i,j);
    }
    auto it = gInter.find(i);
    if(it == gInter.end()) {
        return nullptr;;
    } else {
        auto& dict = it->second;
        auto sit = dict.find(j);
        if(sit != dict.end()) {
            return sit->second;
        } else {
            return nullptr;
        }
    }
}
void InitInter(const vector<Line>& lines) {
    for(auto i = 0; i < lines.size(); i++) {
        auto& l = lines[i];
        for(auto j = i + 1; j < lines.size(); j++) {
            auto inter = Intersection(l, lines[j]);
            if(inter) {
                gInter[i][j] = inter;
            }
        }
    }
}
// 并集
bool Union(Line& l, const Line* r) {
    if(l.e + 1 < r->s) {
        return false;
    }
    if(r->e > l.e) {
        l.e = r->e;
    }
    return true;
}

// 交集是否覆盖1~n
bool IsUnionConver(vector<const Line*>& lines, int n) {
    if(lines.size() == 0) {
        return false;
    }
    sort(lines.begin(), lines.end(), [](const Line*& l, const Line*& r) {
        return l->s < r->s;
    });
    Line all = *lines[0];
    if(all.s != 1) {
        return false;
    }
    if(all.e == n) {
        return true;
    }
    for(auto i = 1; i < lines.size(); i++) {
        auto l = lines[i];
        if(!Union(all, l)) {
            return false;
        }
        if(all.e == n) {
            return true;
        }
    }
    return false;
}

bool Check(vector<int>& pick, int n) {
    if(pick.size() < 2) {
        return false;
    }
    vector<const Line*> unions;
    for(auto i = 0; i < pick.size(); i++) {
        for(auto j = i+1; j < pick.size(); j++) {
            auto inter = GetInter(pick[i],pick[j]);
            if(inter) {
                unions.push_back(inter);
            }
        }
    }
    return IsUnionConver(unions, n);
}
int64_t valid = 0;
void Dfs(int cnt, int i, vector<int>& pick, int n) {
    if(i == cnt) {
        if(Check(pick, n)) {
            valid++;
            const int p = 998244353;
            valid %= p;
        }
        return;
    }
    pick.push_back(i);
    Dfs(cnt, i+1, pick, n);
    pick.pop_back();
    Dfs(cnt, i+1, pick, n);
}

int main() {
    int n, m;
    cin >>n >> m;
    vector<Line> l(m);
    for(auto& v : l) {
        cin >> v;
    }
    InitInter(l);
    vector<int> pick;
    Dfs(m, 0, pick, n);
    cout << valid << endl;
}
// 64 位输出请用 printf("%lld")