SHARE
TWEET

Untitled

a guest Nov 19th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long dp[100001][4];
  6. long long a[100001][2];
  7.  
  8. int main() {
  9.     long long n,k,x,y;
  10.     long long INF = 1000000007;
  11.     cin >> n >> k;
  12.     for (int i = 0; i < k; i++) {
  13.         cin >> x >> y;
  14.         a[x - 1][y - 1] = 1;
  15.     }
  16.     if (a[0][0] == 0 && a[0][1] == 0) {
  17.         dp[0][1] = 1;
  18.         dp[0][2] = 1;
  19.         dp[0][3] = 2;
  20.     }
  21.     if (a[0][0] == 0 && a[0][1] == 1) {
  22.         dp[0][3] = 1;
  23.         dp[0][1] = 1;
  24.     }
  25.     if (a[0][0] == 1 && a[0][1] == 0) {
  26.         dp[0][3] = 1;
  27.         dp[0][2] = 1;
  28.     }
  29.     if (a[0][0] == 1 && a[0][1] == 1)
  30.         dp[0][3] = 1;
  31.     for (int i = 1; i < n; i++) {
  32.         if (a[i][0] == 0 && a[i][1] == 0) {
  33.             dp[i][0] = dp[i - 1][3] % INF;
  34.             dp[i][1] = (dp[i - 1][3] + dp[i - 1][2]) % INF;
  35.             dp[i][2] = dp[i][1] % INF;
  36.             if (i > 1)
  37.                 dp[i][3] = (2*dp[i - 1][3] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 2][3]) % INF;
  38.             else
  39.                 dp[i][3] = (2*dp[i - 1][3] + dp[i - 1][1] + dp[i - 1][2] + 1) % INF;
  40.         }
  41.         if (a[i][0] == 0 && a[i][1] == 1) {
  42.             dp[i][3] = (dp[i - 1][3] + dp[i - 1][1]) % INF;
  43.             dp[i][1] = dp[i - 1][3] % INF;
  44.         }
  45.         if (a[i][0] == 1 && a[i][1] == 0) {
  46.             dp[i][3] = (dp[i - 1][3] + dp[i - 1][2]) % INF;
  47.             dp[i][2] = dp[i - 1][3] % INF;
  48.         }
  49.         if (a[i][0] == 1 && a[i][1] == 1)
  50.             dp[i][3] = dp[i - 1][3] % INF;
  51.     }
  52.     cout << dp[n - 1][3];
  53. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top