Guest User

D

a guest
May 19th, 2013
433
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <utility>
  4. #include <cassert>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. const int MOD = 1000000007, N = 1000005;
  10.  
  11. int n, m, k, ans, degs[N];
  12.  
  13. #define forn(i,n) for(int i = 0; i < (int) n; i++)
  14.  
  15. inline int add(int a, int b) { a += b; if (a >= MOD) a -= MOD; return a;}
  16.  
  17. int main(){
  18.     degs[0] = 1;
  19.     forn(i, N) {
  20.         if (!i) continue;
  21.         degs[i] = add(degs[i-1], degs[i-1]);
  22.     }
  23.     scanf("%d %d %d\n", &n, &m, &k);
  24.     vector < pair<int,int> > edges;
  25.     forn(i, m) {
  26.         int a, b;
  27.         scanf("%d %d", &a, &b);
  28.         if (b - a != 1 && b - a != k + 1) {
  29.             puts("0");
  30.             return 0;
  31.         }
  32.         if (b - a == k + 1) edges.push_back(make_pair(a, b));
  33.     }
  34.     sort(edges.begin(), edges.end()); m = edges.size();
  35.     if (k == 0 || k >= n - 1) {
  36.         puts("1");
  37.         return 0;
  38.     }
  39.     forn(i, m) {
  40.         if (!(edges[i].first >= edges[0].first && edges[i].first < edges[0].second)) {
  41.             puts("0");
  42.             return 0;
  43.         }
  44.     }
  45.         if (edges.size() == 0) ++ans;
  46.     forn(i, n) {
  47.         int f = i + 1, s = i + k + 2, cnt = m;
  48.         if (s > n || (m > 0 && f > edges[0].first)) break;
  49.         if (m > 0 && !(f <= edges[0].first && edges[m-1].first < s)) continue;
  50.         if (m > 0 && f == edges[0].first) cnt--;
  51.         s = min(s, n - k);
  52.         ans = add(ans,degs[s - f - cnt - 1]);
  53.     }
  54.     printf("%d\n", ans);
  55. }
RAW Paste Data