wordpress文字博客主题,上海网站seo外包,产品盘网站建设,镇江城乡建设网站首页题目链接 Count Arrays 题意 给定$n$和$m$个区间。若一个长度为$n$的$01$序列满足对于每一个给定的区间中至少有一个位置是$0$#xff0c; 那么这个$01$序列满足条件。求有多少满足条件的$01$序列。 设$f[i]$为考虑到第$i$位的时候#xff0c;有多少满足条件的$01$序列。 则…题目链接 Count Arrays 题意 给定$n$和$m$个区间。若一个长度为$n$的$01$序列满足对于每一个给定的区间中至少有一个位置是$0$ 那么这个$01$序列满足条件。求有多少满足条件的$01$序列。 设$f[i]$为考虑到第$i$位的时候有多少满足条件的$01$序列。 则转移方程为$f[i] ∑f[j] (j i)$意义为当$f[j]$转移给了$f[i]$时相当于贡献了$[j1,i-1]$这段区间都为$1$的方案数。 于是按照题目给定的区间预处理出每个数的转移范围。 显然当$i$递增的时候在转移范围之内的$j$的最小值是不下降的。 那么就可以通过这个单调性做到$O(n)$了。 #include bits/stdc.husing namespace std;#define rep(i, a, b) for (int i(a); i (b); i)
#define dec(i, a, b) for (int i(a); i (b); --i)const int N 1e5 10;
const int mod 1e9 7;int n, m;
int c[N], f[N];
int now, cnt;int main(){scanf(%d%d, n, m);rep(i, 1, m){int x, y;scanf(%d%d, x, y);c[y 1] max(c[y 1], x);}f[now 0] cnt 1;rep(i, 1, n 1){while (now c[i]) cnt (cnt - f[now] mod) % mod;f[i] cnt;(cnt f[i]) % mod;}printf(%d\n, f[n 1]);return 0;
}转载于:https://www.cnblogs.com/cxhscst2/p/8401829.html
