Source Code
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

template<int MOD>
struct Integral {
  int v_ = 0;
 
  // Implicit conversion is allowed.
  Integral(int v) : v_(norm(v)) {}
  Integral(long long v) : v_(norm(v)) {}
  Integral(unsigned int v) : v_(norm(v)) {}
  Integral(unsigned long long v) : v_(norm(v)) {}
  Integral() = default;
  ~Integral() = default;
 
  template<typename T> T norm(T v) const {
    if constexpr(sizeof(T) > sizeof(MOD)) {
      v %= MOD;
      if (v < 0) v += MOD;
    } else {
      if (v >= MOD) v -= MOD;
      if (v < 0) v += MOD;
      if (v >= MOD || v < 0) {
        v %= MOD;
        if (v < 0) v += MOD;
      }
    }
    return v;
  }
 
  int val() const { return v_; }
  Integral& operator+=(const Integral& rhs) { v_ += rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
  Integral& operator-=(const Integral& rhs) { v_ += MOD - rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
  Integral& operator*=(const Integral& rhs) { v_ = v_ * 1LL * rhs.val() % MOD; return *this; }
  Integral& operator/=(const Integral& rhs) { v_ = v_ * 1LL * rhs.inv().val() % MOD; return *this; }
  Integral operator+(const Integral& rhs) const { Integral ret = *this; return ret += rhs; }
  Integral operator-(const Integral& rhs) const { Integral ret = *this; return ret -= rhs; }
  Integral operator*(const Integral& rhs) const { Integral ret = *this; return ret *= rhs; }
  Integral operator/(const Integral& rhs) const { Integral ret = *this; return ret /= rhs; }
  bool operator==(const Integral& rhs) const { return val() == rhs.val(); }
  bool operator!=(const Integral& rhs) const { return !(*this == rhs); }
  const Integral operator-() const { return Integral(-val()); }
  const Integral& operator++() { v_ += 1; if (v_ >= MOD) v_ -= MOD; return *this; }
  const Integral operator++(int) { Integral ret = *this; ++(*this); return ret; }
  const Integral& operator--() { v_ += MOD - 1; if (v_ >= MOD) v_ -= MOD; return *this; }
  const Integral operator--(int) { Integral ret = *this; --(*this); return ret; }
 
  Integral power(long long b) const {
    long long ret = 1 % MOD, a = v_;
    for ( ; b; b >>= 1, a = a * a % MOD) if (b & 1) ret = ret * a % MOD; return ret;
  }
  Integral inv() const { return power(MOD - 2); }
 
  std::string to_string() const { return std::string("{") + std::to_string(val()) + "}"; }
};

template<int MOD, bool kAllowBruteForce = false>
struct Binomial final {
  std::vector<Integral<MOD>> fact, inv_fact;
 
  explicit Binomial(int n = 0) : fact(n + 1), inv_fact(n + 1) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
    inv_fact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) inv_fact[i - 1] = inv_fact[i] * i;
  }
  ~Binomial() = default;
 
  template<typename T>
  Integral<MOD> operator()(T a, T b) const {
    if (a < b || b < 0) return 0;
    if (a < fact.size()) return fact[a] * inv_fact[b] * inv_fact[a - b];
    if constexpr(!kAllowBruteForce) {
      throw std::out_of_range("Binomial");
    } else {
      b = std::min(b, a - b);
      Integral<MOD> ret = 1;
      for (T i = 1; i <= b; ++i) {
        ret = ret * (a + 1 - i);
        if (i < inv_fact.size()) {
          ret = ret * inv_fact[i] * fact[i - 1];
        } else {
          ret = ret / i;
        }
      }
      return ret;
    }
  }
};

const int MOD = 1e9 + 7;
using Mint = Integral<MOD>;
using Binom = Binomial<MOD>;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> p(n);
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
  }
  vector<int> q(n);
  for (int i = 0; i < n; ++i) {
    cin >> q[i];
  }
  vector<int> cntMoves(n);
  for (int i = 0; i < n; ++i) {
    int delta = q[i] - p[i];
    if (delta % (i + 1) != 0 || delta < 0) {
      cout << 0 << '\n';
      return 0;
    }
    cntMoves[i] = delta / (i + 1);
  }
  int totalMoves = accumulate(cntMoves.begin(), cntMoves.end(), 0);
  Binom binom(totalMoves);
  Mint ans = binom.fact[totalMoves];
  for (int cnt : cntMoves) {
    ans *= binom.inv_fact[cnt];
  }
  cout << ans.val() << '\n';
  return 0;
}
Copy
N-dimensions abdulrahman_aj
GNU G++17
86 ms
22.0 MB
Accepted