提出 #830351

---

ソースコード 拡げる

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::size_t powmod (std::size_t x, std::size_t n, std::size_t p) {
  if (n == 0) { return 0; }
  if (n == 1) { return x % p; }
  if (n % 2 == 0) {
    std::size_t y = powmod(x, n / 2, p);
    return (y * y) % p;
  }
  return (powmod(x, n / 2, p) * powmod(x, n / 2 + 1, p)) % p;
}

int main () { 

  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  std::string line;
  std::getline(std::cin, line);

  char * p = &*line.begin();

  int N = std::strtol(p, &p, 10);

  std::vector<int> A(N, 0);

  std::getline(std::cin, line);
  p = &*line.begin();
  int A0 = std::strtol(p, &p, 10);

  for (int i = 1; i < N; ++i) {
    int a = std::strtol(p, &p, 10);
    A[a] += 1;
  }

  if (A0 != 0) {
    std::cout << 0 << std::endl;
    return 0;
  }

  if (A[0] != 0) {
    std::cout << 0 << std::endl;
    return 0;
  }

  std::size_t count = 1;
  std::size_t P = 1000000007;

  if (A[1] > 1) {
    std::size_t n = (A[1] * (A[1] - 1)) / 2;
    count = (count * powmod(2, n, P)) % P;
  }

  for (int i = 2; i < N; ++i) {
    if (A[i] == 0) {
      for (int j = i + 1; j < N; ++j) {
        if (A[j] != 0) {
          std::cout << 0 << std::endl;
          return 0;
        }
      }
      break;
    }

    if (A[i] > 1) { 
      std::size_t n = (A[i] * (A[i] - 1)) / 2;
      count = (count * powmod(2, n, P)) % P;
    }
  
    std::size_t n = powmod(2, A[i - 1], P) - 1;
    count = (count * powmod(n, A[i], P)) % P;
  }

  std::cout << count << std::endl;
}

提出情報

ジャッジ結果