HJ155 小A的线段（easy version）

题目题解(7)讨论(3)排行较难 通过率52.11% 时间限制1秒 空间限制256M知识点dfs校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述在坐标轴的整数点 1∼n1∼n 上给出 mm 条闭区间线段第 ii 条线段用其端点 [ sti, edi ][sti​,edi​] 描述。现在要从这 mm 条线段中选择若干条使得每个整数点被至少两条所选线段覆盖。求满足条件的选择方案数量两种方案视为不同当且仅当存在某条线段在两方案中的选/不选状态不同。答案对 P998 244 353P998244353 取模。输入描述第一行输入整数 n,m (2≦n≦105, 1≦m≦10)n,m(2≦n≦105, 1≦m≦10)。随后 mm 行每行两个整数 sti,edisti​,edi​1≦stiedi≦n1≦sti​edi​≦n 描述一条线段。输出描述输出满足条件的方案数对 998244353998244353 取模的结果。示例1输入5 4 4 5 1 5 3 5 1 4复制输出3#include bits/stdc.h using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint st(m), ed(m); for(int i 0; i m; i) cin st[i] ed[i]; // 收集断点构造等价区间 vectorint bp; bp.push_back(1); bp.push_back(n 1); for(int i 0; i m; i){ bp.push_back(st[i]); bp.push_back(ed[i] 1); } sort(bp.begin(), bp.end()); bp.erase(unique(bp.begin(), bp.end()), bp.end()); // 建立 [1,n] 内的区间并计算覆盖掩码 vectorint covmask; for(int j 0; j 1 (int)bp.size(); j){ int l max(bp[j], 1), r min(bp[j 1] - 1, n); if(l r) continue; int mask 0; for(int i 0; i m; i) if(st[i] l l ed[i]) mask | (1 i); covmask.push_back(mask); } // 枚举所有子集 long long ans 0; for(int mask 0; mask (1 m); mask){ bool ok true; for(int cm : covmask){ if(__builtin_popcount(cm mask) 2){ ok false; break; } } if(ok) ans; } cout ans % 998244353 \n; }