comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: test/atcoder/arc117_c.test.cpp

Depends on

Code

// verification-helper: PROBLEM https://atcoder.jp/contests/arc117/tasks/arc117_c

#include "src/cpp-template/header/size-alias.hpp"
#include "src/math/modular-arithmetic/small-mod-combination.hpp"
#include "src/math/modular-arithmetic/static-modint.hpp"

#include <iostream>
#include <string>

namespace luz {

  void main_() {
    using mint = StaticPrimeModInt< 3 >;
    SmallModCombination< mint > mc;

    usize n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    auto convert = [](char c) {
      switch (c) {
        case 'B':
          return 0;
        case 'W':
          return 1;
        case 'R':
          return 2;
        default:
          exit(-1);
      }
    };

    mint sum;
    for (usize i = 0; i < n; i++) {
      sum +=
          (n & 1 ? 1 : -1) * convert(s[i]) * mc.combination(n - 1, i);
    }

    auto inverse = [](mint x) {
      switch (x.val()) {
        case 0:
          return 'B';
        case 1:
          return 'W';
        case 2:
          return 'R';
        default:
          exit(-1);
      }
    };

    std::cout << inverse(sum) << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}
#line 1 "test/atcoder/arc117_c.test.cpp"
// verification-helper: PROBLEM https://atcoder.jp/contests/arc117/tasks/arc117_c

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 2 "src/math/modular-arithmetic/small-mod-combination.hpp"

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32  = std::int32_t;
  using i64  = std::int64_t;
  using i128 = __int128_t;

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 2 "src/math/modular-arithmetic/modular-combinatorics.hpp"

#line 2 "src/cpp-template/header/rep.hpp"

#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 5 "src/math/modular-arithmetic/modular-combinatorics.hpp"

#include <vector>

namespace luz {

  template < typename mint >
  class Combinatorics {
    static usize bound;
    static std::vector< mint > fact, finv, inv;

    static void expand(usize n) {
      n += 1;
      if (fact.size() >= n) return;

      if (bound == 0) bound = 1;

      fact.resize(n, mint(1));
      finv.resize(n, mint(1));
      inv.resize(n, mint(1));

      for (usize i: rep(bound, n)) {
        fact[i] = fact[i - 1] * i;
      }

      finv.back() = mint(1) / fact.back();
      for (usize i: rrep(bound, n)) {
        finv[i - 1] = finv[i] * i;
      }

      for (usize i: rep(bound, n)) {
        inv[i] = finv[i] * fact[i - 1];
      }

      bound = n;
    }

   public:
    explicit Combinatorics(usize n = 0) {
      expand(n);
    }

    static mint factorial(usize n) {
      expand(n);
      return fact[n];
    }

    static mint factorial_inverse(usize n) {
      expand(n);
      return finv[n];
    }

    static mint inverse(usize n) {
      expand(n);
      return inv[n];
    }

    static mint permutation(isize n, isize r) {
      if (r < 0 or n < r) return 0;

      expand(n);
      return fact[n] * finv[n - r];
    }

    static mint combination(isize n, isize r) {
      if (r < 0 or n < r) return 0;

      expand(n);
      return fact[n] * finv[r] * finv[n - r];
    }

    static mint combination_with_repetitions(isize n, isize r) {
      if (n < 0 or r < 0) return 0;
      return (r ? combination(n + r - 1, r) : 1);
    }

    static mint P(isize n, isize r) {
      return permutation(n, r);
    }

    static mint C(isize n, isize r) {
      return combination(n, r);
    }

    static mint H(isize n, isize r) {
      return combination_with_repetitions(n, r);
    }
  };

  template < typename mint >
  usize Combinatorics< mint >::bound = 0;

  template < typename mint >
  std::vector< mint > Combinatorics< mint >::fact =
      std::vector< mint >();

  template < typename mint >
  std::vector< mint > Combinatorics< mint >::finv =
      std::vector< mint >();

  template < typename mint >
  std::vector< mint > Combinatorics< mint >::inv =
      std::vector< mint >();

} // namespace luz
#line 6 "src/math/modular-arithmetic/small-mod-combination.hpp"

namespace luz {

  template < typename modint >
  class SmallModCombination {
    static constexpr u32 mod = modint::get_mod();
    Combinatorics< modint > mc;

   public:
    SmallModCombination(): mc(mod - 1) {}

    modint combination(isize n, isize r) {
      if (r < 0 or n < r) return 0;

      modint result(1);
      while (n) {
        result *= mc.combination(n % mod, r % mod);
        n /= mod;
        r /= mod;
      }

      return result;
    }

    modint C(isize n, isize r) {
      return combination(n, r);
    }
  };

} // namespace luz
#line 2 "src/math/modular-arithmetic/static-modint.hpp"

#line 4 "src/math/modular-arithmetic/static-modint.hpp"

#include <cassert>
#include <iostream>

namespace luz {

  template < u32 mod >
  class StaticPrimeModInt {
    using modint = StaticPrimeModInt;

    u32 v;

   public:
    StaticPrimeModInt(): v(0) {}

    template < typename T >
    StaticPrimeModInt(T v_) {
      i64 x = (i64)(v_ % (i64)mod);
      if (x < 0) x += mod;
      v = (u32)x;
    }

    u32 val() const {
      return v;
    }

    modint &operator+=(const modint &rhs) {
      v += rhs.v;
      if (v >= mod) v -= mod;
      return *this;
    }

    modint &operator-=(const modint &rhs) {
      v += mod - rhs.v;
      if (v >= mod) v -= mod;
      return *this;
    }

    modint &operator*=(const modint &rhs) {
      v = (u32)(u64(1) * v * rhs.v % mod);
      return *this;
    }

    modint &operator/=(const modint &rhs) {
      *this *= rhs.inverse();
      return *this;
    }

    modint operator+() const {
      return *this;
    }

    modint operator-() const {
      return modint() - *this;
    }

    friend modint operator+(const modint &lhs, const modint &rhs) {
      return modint(lhs) += rhs;
    }

    friend modint operator-(const modint &lhs, const modint &rhs) {
      return modint(lhs) -= rhs;
    }

    friend modint operator*(const modint &lhs, const modint &rhs) {
      return modint(lhs) *= rhs;
    }

    friend modint operator/(const modint &lhs, const modint &rhs) {
      return modint(lhs) /= rhs;
    }

    friend bool operator==(const modint &lhs, const modint &rhs) {
      return lhs.v == rhs.v;
    }

    friend bool operator!=(const modint &lhs, const modint &rhs) {
      return lhs.v != rhs.v;
    }

    modint pow(i64 n) const {
      assert(0 <= n);
      modint x = *this, r = 1;
      while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
      }
      return r;
    }

    modint inverse() const {
      assert(v != 0);
      return pow(mod - 2);
    }

    static constexpr u32 get_mod() {
      return mod;
    }

    friend std::ostream &operator<<(std::ostream &os,
                                    const modint &m) {
      os << m.val();
      return os;
    }
  };

  using modint998244353  = StaticPrimeModInt< 998244353 >;
  using modint1000000007 = StaticPrimeModInt< 1000000007 >;

} // namespace luz
#line 6 "test/atcoder/arc117_c.test.cpp"

#line 8 "test/atcoder/arc117_c.test.cpp"
#include <string>

namespace luz {

  void main_() {
    using mint = StaticPrimeModInt< 3 >;
    SmallModCombination< mint > mc;

    usize n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    auto convert = [](char c) {
      switch (c) {
        case 'B':
          return 0;
        case 'W':
          return 1;
        case 'R':
          return 2;
        default:
          exit(-1);
      }
    };

    mint sum;
    for (usize i = 0; i < n; i++) {
      sum +=
          (n & 1 ? 1 : -1) * convert(s[i]) * mc.combination(n - 1, i);
    }

    auto inverse = [](mint x) {
      switch (x.val()) {
        case 0:
          return 'B';
        case 1:
          return 'W';
        case 2:
          return 'R';
        default:
          exit(-1);
      }
    };

    std::cout << inverse(sum) << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}
Back to top page