题意

给你一个逆序图(令图G为有n个节点的图，编号为1~n。对于满足 1≤i<j≤n的一对i和j，如果有a[i]>a[j]，那么在G中编号为i和j的节点之间连一条边。 得到的图G被称为逆序图。)，求图G中有多少个点集既是独立点集又是覆盖集。

分析

我们可以先考虑将逆序图还原成原来的序列，然后看看独立点集和覆盖集要满足的条件是怎样。
独立点集：点集中不存在在原图中有边直接相连的点对。就是说点集中不存在序列里的逆序对，点集中的点在原序列里是一个上升序列。
覆盖集：原图中的点都在点集中或与点集中的点任意点有边直接相连。也就是所有序列中所有没选的数，都与选的数构成至少一对逆序对，即在它前面选了一个比它大的数，或在它后面选了一个比它小的数。
将两个结合起来看：若点集中在序列相邻的两个数ai,aj,(i<j,ai<aj),有∀ak<ai或ak>aj,k∈(i,j),即不存在ai<ak<aj,k∈(i,j)
我们设f[i]为以第i个数为点集结尾的方案数，则f[i]=∑f[j]

j满足上述条件。

现在问题变成怎么将逆序图转化成序列了。序列从左往右做，我们知道每个位置在它后面比它小的数有

x个，那么这个位置的数为当前未选的第x+1个数，证明显然。

答案为

∑f[i],

i满足∀ai>aj,j∈(i,n]

#include <cstdio>
#include <algorithm>
using namespace std;const int N = 1e3 + 10;
const int P = 1e9 + 7;
int a[N],c[N],f[N];
int n,m;
bool p[N];void init() {scanf("%d%d",&n,&m);for (int i = 1;i <= m;i ++) {int x,y;scanf("%d%d",&x,&y);if (x < y) c[x] ++;else c[y] ++;}
}void build() {for (int i = 1;i <= n;i ++) {c[i] ++;int j;for (j = 1;j <= n;j ++) if (!p[j]) {c[i] --;if (!c[i]) break;}a[i] = j;p[j] = true;}
}void solve() {f[0] = 1;for (int i = 1;i <= n;i ++) {int cur = -1;for (int j = i - 1;j >= 0;j --) {if (a[j] < a[i] && cur < a[j]) {f[i] = (f[i] + f[j]) % P;}if (a[j] < a[i]) cur = max(cur,a[j]); }}int ans = 0;for (int i = 1;i <= n;i ++) {int flag = 1;for (int j = i + 1;j <= n;j ++) if (a[j] > a[i]) {flag = 0;break;}ans = (ans + flag * f[i]) % P;}printf("%d",ans);
}int main() {init();build();solve();
}