Submission #5878618


Source Code Expand

Copy
#define DEBUG 0
/**
 * File    : C.cpp
 * Author  : Kazune Takahashi
 * Created : 6/11/2019, 7:13:20 PM
 * Powered by Visual Studio Code
 */
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <functional>
#include <random>
#include <chrono>
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
typedef long long ll;
void Yes()
{
  cout << "Yes" << endl;
  exit(0);
}
void No()
{
  cout << "No" << endl;
  exit(0);
}
const int MAX_SIZE = 1000010;
class mint
{
public:
  static ll MOD;
  ll x;
  mint() : x(0) {}
  mint(ll x) : x(x % MOD) {}
  mint operator-() const { return mint(0) - *this; }
  mint &operator+=(const mint &a)
  {
    if ((x += a.x) >= MOD)
    {
      x -= MOD;
    }
    return *this;
  }
  mint &operator-=(const mint &a) { return *this += -a; }
  mint &operator*=(const mint &a)
  {
    (x *= a.x) %= MOD;
    return *this;
  }
  mint &operator/=(const mint &a) { return (*this *= power(MOD - 2)); }
  mint operator+(const mint &a) const { return mint(*this) += a; }
  mint operator-(const mint &a) const { return mint(*this) -= a; }
  mint operator*(const mint &a) const { return mint(*this) *= a; }
  mint operator/(const mint &a) const { return mint(*this) /= a; }
  bool operator<(const mint &a) const { return x < a.x; }
  bool operator==(const mint &a) const { return x == a.x; }
  const mint power(ll N)
  {
    if (N == 0)
    {
      return 1;
    }
    else if (N % 2 == 1)
    {
      return *this * power(N - 1);
    }
    else
    {
      mint half = power(N / 2);
      return half * half;
    }
  }
};
ll mint::MOD = 1e9 + 7;
istream &operator>>(istream &stream, mint &a) { return stream >> a.x; }
ostream &operator<<(ostream &stream, const mint &a) { return stream << a.x; }
mint inv[MAX_SIZE];
mint fact[MAX_SIZE];
mint factinv[MAX_SIZE];
void init()
{
  inv[1] = 1;
  for (int i = 2; i < MAX_SIZE; i++)
  {
    inv[i] = (-inv[mint::MOD % i]) * (mint::MOD / i);
  }
  fact[0] = factinv[0] = 1;
  for (int i = 1; i < MAX_SIZE; i++)
  {
    fact[i] = mint(i) * fact[i - 1];
    factinv[i] = inv[i] * factinv[i - 1];
  }
}
mint choose(int n, int k)
{
  if (n >= 0 && k >= 0 && n - k >= 0)
  {
    return fact[n] * factinv[k] * factinv[n - k];
  }
  return 0;
}
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
// const double epsilon = 1e-10;
// const ll infty = 1000000000000000LL;
// const int dx[4] = {1, 0, -1, 0};
// const int dy[4] = {0, 1, 0, -1};

ll N, M;
bool ok[100010];
mint dp[100010];

int main()
{
  // init();
  cin >> N >> M;
  fill(ok, ok + 100010, true);
  for (auto i = 0; i < M; i++)
  {
    int a;
    cin >> a;
    ok[a] = false;
  }
  dp[0] = 1;
  for (auto i = 0; i < N; i++)
  {
    if (ok[i + 1])
    {
      dp[i + 1] += dp[i];
    }
    if (ok[i + 2])
    {
      dp[i + 2] += dp[i];
    }
  }
  cout << dp[N] << endl;
}

Submission Info

Submission Time
Task C - Typical Stairs
User kazunetakahashi
Language C++14 (GCC 5.4.1)
Score 300
Code Size 3239 Byte
Status
Exec Time 43 ms
Memory 24576 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 300 / 300 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 8 ms 24576 KB
02.txt 8 ms 24576 KB
03.txt 8 ms 24576 KB
04.txt 8 ms 24576 KB
05.txt 8 ms 24576 KB
06.txt 8 ms 24576 KB
07.txt 8 ms 24576 KB
08.txt 8 ms 24576 KB
09.txt 8 ms 24576 KB
10.txt 8 ms 24576 KB
11.txt 8 ms 24576 KB
12.txt 8 ms 24576 KB
13.txt 8 ms 24576 KB
14.txt 8 ms 24576 KB
15.txt 8 ms 24576 KB
16.txt 35 ms 24576 KB
17.txt 9 ms 24576 KB
18.txt 16 ms 24576 KB
19.txt 15 ms 24576 KB
20.txt 8 ms 24576 KB
21.txt 13 ms 24576 KB
22.txt 8 ms 24576 KB
23.txt 18 ms 24576 KB
24.txt 11 ms 24576 KB
25.txt 11 ms 24576 KB
26.txt 9 ms 24576 KB
27.txt 9 ms 24576 KB
28.txt 43 ms 24576 KB
29.txt 26 ms 24576 KB
30.txt 9 ms 24576 KB
31.txt 19 ms 24576 KB
32.txt 22 ms 24576 KB
33.txt 23 ms 24576 KB
s1.txt 8 ms 24576 KB
s2.txt 8 ms 24576 KB
s3.txt 8 ms 24576 KB