＜P5464 缩小社交圈＞

题目描述社交圈子里有 n 个人每个人都有一个 SAN 值范围 [li​,ri​]。当两个人的 SAN 值交集不为空时这两个人有 PY 关系。现在希望从社交圈子里面挑选出一些人组成一个集合 S如果将所有集合内的人中有 PY 关系的那一对人都连上边则 S 刚好成为一个树森林不行哦。请问有多少种可以选择的方案由于答案可能很大请对 1097 取模。输入格式第一行一个整数 n。接下来 n 行每行 2 个整数表示这个人的 SAN 值区间。输出格式一行一个整数表示答案。输入输出样例输入 #1复制3 1 5 2 7 4 8输出 #1复制6说明/提示对于20%的数据满足 n≤18 。对于40%的数据满足 n≤50对于60%的数据满足 n≤200对于100%的数据满足 n≤2000,1≤li​ri​≤4000代码实现#includebits/stdc.h using namespace std; #define int long long const int mod1e97; inline void rd(int x) { x0;int p1;char chgetchar(); while(ch0||ch9){if(ch-)p-p;chgetchar();} while(ch0ch9)x(x1)(x3)(ch-0),chgetchar(); x*p; } int n,dp[2005][2005],pre[2005][2005],sl[4005],sr[4005]; struct nd {int l,r;}p[2005]; bool cmp(const nda,const ndb) { if(a.l!b.l)return a.lb.l; return a.rb.r; } int mn(int x,int y) {return xy?x:y;} int mx(int x,int y) {return xy?x:y;} void add(int x,int y) { xy; if(xmod)x-mod; if(x0)xmod; } signed main() { rd(n); for(int i1;in;i) {rd(p[i].l);rd(p[i].r);} sort(p1,pn1,cmp); for(int i1;in;i) for(int ji1;jn;j) if(p[i].rp[j].l)dp[i][j]1; p[n1].l99999999; sl[0]0,sr[0]0; for(int i1;i4000;i) { sl[i]sl[i-1]; sr[i]sr[i-1]; while(p[sl[i]].li)sl[i]; while(p[sr[i]1].li)sr[i]; } for(int i1;in;i) { for(int ji1;jn;j) { if(!dp[i][j])continue; add(pre[i][j],pre[i][j-1]); add(dp[i][j],pre[i][j]); if(p[i].rp[j].r)continue; int xmn(p[i].r,p[j].r); int ymx(p[i].r,p[j].r); int Lsl[x1]; int Rsr[y]; if(LR)continue; if(p[i].rp[j].r)add(pre[i][L],dp[i][j]),add(pre[i][R1],-dp[i][j]); else add(pre[j][L],dp[i][j]),add(pre[j][R1],-dp[i][j]); } } int ansn; for(int i1;in;i) for(int ji1;jn;j) add(ans,dp[i][j]); printf(%lld\n,ans); return 0; }