結果
問題 | No.1035 Color Box |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:03:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 4,352 bytes |
コンパイル時間 | 1,167 ms |
コンパイル使用メモリ | 76,732 KB |
最終ジャッジ日時 | 2025-01-09 23:49:56 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <iostream>#include <algorithm>#include <utility>#include <vector>#include <numeric>template <class T, class U>inline bool chmin(T &lhs, const U &rhs) {if (lhs > rhs) {lhs = rhs;return true;}return false;}template <class T, class U>inline bool chmax(T &lhs, const U &rhs) {if (lhs < rhs) {lhs = rhs;return true;}return false;}// [l, r) from l to rstruct range {struct itr {int i;constexpr itr(int i_): i(i_) { }constexpr void operator ++ () { ++i; }constexpr int operator * () const { return i; }constexpr bool operator != (itr x) const { return i != x.i; }};const itr l, r;constexpr range(int l_, int r_): l(l_), r(std::max(l_, r_)) { }constexpr itr begin() const { return l; }constexpr itr end() const { return r; }};// [l, r) from r to lstruct revrange {struct itr {int i;constexpr itr(int i_): i(i_) { }constexpr void operator ++ () { --i; }constexpr int operator * () const { return i; }constexpr bool operator != (itr x) const { return i != x.i; }};const itr l, r;constexpr revrange(int l_, int r_): l(l_ - 1), r(std::max(l_, r_) - 1) { }constexpr itr begin() const { return r; }constexpr itr end() const { return l; }};template <class T>class modulo_int {public:static constexpr int mod = T::value;static_assert(mod > 0, "mod must be positive");private:long long value;constexpr void normalize() {value %= mod;if (value < 0) value += mod;}public:constexpr modulo_int(long long value_ = 0): value(value_) { normalize(); }constexpr modulo_int operator - () const { return modulo_int(mod - value); }constexpr modulo_int operator ~ () const { return power(mod - 2); }constexpr long long operator () () const { return value; }constexpr modulo_int operator + (const modulo_int &rhs) const { return modulo_int(*this) += rhs; }constexpr modulo_int &operator += (const modulo_int &rhs) {if ((value += rhs.value) >= mod) value -= mod;return (*this);}constexpr modulo_int operator - (const modulo_int &rhs) const { return modulo_int(*this) -= rhs; }constexpr modulo_int &operator -= (const modulo_int &rhs) {if ((value += mod - rhs.value) >= mod) value -= mod;return (*this);}constexpr modulo_int operator * (const modulo_int &rhs) const { return modulo_int(*this) *= rhs; }constexpr modulo_int &operator *= (const modulo_int &rhs) {(value *= rhs.value) %= mod;return (*this);}constexpr modulo_int operator / (const modulo_int &rhs) const { return modulo_int(*this) /= rhs; }constexpr modulo_int &operator /= (const modulo_int &rhs) {return (*this) *= ~rhs;}constexpr bool operator == (const modulo_int &rhs) const {return value == rhs();}constexpr bool operator != (const modulo_int &rhs) const {return value != rhs();}constexpr modulo_int power (unsigned long long pow) const {modulo_int result(1), mult(*this);while (pow > 0) {if (pow & 1) result *= mult;mult *= mult;pow >>= 1;}return result;}friend std::istream &operator >> (std::istream &stream, modulo_int &lhs) {stream >> lhs.value;lhs.normalize();return stream;}friend std::ostream &operator << (std::ostream &stream, const modulo_int &rhs) {return stream << rhs.value;}};template <class T>class factorials {public:using value_type = T;public:std::vector<value_type> fact, fact_inv;factorials(int size_ = 200000): fact(size_ + 1), fact_inv(size_ + 1) {fact[0] = 1;for (int i = 1; i <= size_; ++i) {fact[i] = fact[i - 1] * value_type(i);}fact_inv[size_] = ~fact[size_];for (int i = size_; i > 0; --i) {fact_inv[i - 1] = fact_inv[i] * value_type(i);}}value_type operator () (int n, int r) const {return fact[n] * fact_inv[n - r] * fact_inv[r];}};using modint = modulo_int<std::integral_constant<int, 1000000007>>;factorials<modint> fact(100000);int main() {int N, M;std::cin >> N >> M;modint ans = modint(M).power(N);for (int i: range(1, M)) {if (i % 2 == 1) {ans -= fact(M, i) * modint(M - i).power(N);}else {ans += fact(M, i) * modint(M - i).power(N);}}std::cout << ans << '\n';return 0;}