結果
| 問題 | No.1035 Color Box |
| ユーザー |
 kyo1
|
| 提出日時 | 2020-05-12 20:07:19 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 13 ms / 2,000 ms |
| コード長 | 6,790 bytes |
| コンパイル時間 | 1,887 ms |
| コンパイル使用メモリ | 171,144 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-09-13 20:27:45 |
| 合計ジャッジ時間 | 3,165 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T>T inverse(T a, T m) {T u = 0, v = 1;while (a != 0) {T t = m / a;m -= t * a;u -= t * v;std::swap(a, m);std::swap(u, v);}assert(m == 1);return u;}template <typename T>class Modular {public:using Type = typename std::decay<decltype(T::value)>::type;constexpr Modular() : value() {}template <typename U>Modular(const U &x) : value(normalize(x)) {}template <typename U>Type normalize(const U &x) {Type v;if (-mod() <= x && x < mod()) {v = static_cast<Type>(x);} else {v = static_cast<Type>(x % mod());}if (v < 0) v += mod();return v;}const Type &operator()() const { return value; }template <typename U>explicit operator U() const {return static_cast<U>(value);}constexpr static Type mod() { return T::value; }Modular &operator+=(const Modular &rhs) {if ((value += rhs.value) >= mod()) value -= mod();return *this;}Modular &operator-=(const Modular &rhs) {if ((value -= rhs.value) < 0) value += mod();return *this;}template <typename U>Modular &operator+=(const U &rhs) {return *this += Modular(rhs);}template <typename U>Modular &operator-=(const U &rhs) {return *this -= Modular(rhs);}Modular &operator++() { return *this += 1; }Modular &operator--() { return *this -= 1; }Modular operator++(int) {Modular res(*this);*this += 1;return res;}Modular operator--(int) {Modular res(*this);*this -= 1;return res;}template <typename U = T>typename enable_if<std::is_same<typename Modular<U>::Type, int>::value,Modular>::type &operator*=(const Modular &rhs) {value = normalize(static_cast<int64_t>(value) *static_cast<int64_t>(rhs.value));return *this;}template <typename U = T>typename enable_if<std::is_same<typename Modular<U>::Type, int64_t>::value ||std::is_same<typename Modular<U>::Type, std::int_fast64_t>::value,Modular>::type &operator*=(const Modular &rhs) {value = normalize(static_cast<__int128>(value) *static_cast<__int128>(rhs.value));return *this;}Modular &operator/=(const Modular &rhs) {return *this *= Modular(inverse(rhs.value, mod()));}template <typename U>friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);template <typename U>friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);template <typename U>friend bool operator>(const Modular<U> &lhs, const Modular<U> &rhs);template <typename U>friend std::istream &operator>>(std::istream &stream, Modular<U> &rhs);template <typename U>friend std::ostream &operator<<(std::ostream &stream, const Modular<U> &rhs);private:Type value;};template <typename T>bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) {return lhs.value == rhs.value;}template <typename T, typename U>bool operator==(const Modular<T> &lhs, U rhs) {return lhs == Modular<T>(rhs);}template <typename T, typename U>bool operator==(U lhs, const Modular<T> &rhs) {return Modular<T>(lhs) == rhs;}template <typename T>bool operator!=(const Modular<T> &lhs, const Modular<T> &rhs) {return !(lhs == rhs);}template <typename T, typename U>bool operator!=(const Modular<T> &lhs, U rhs) {return !(lhs == rhs);}template <typename T, typename U>bool operator!=(U lhs, const Modular<T> &rhs) {return !(lhs == rhs);}template <typename T>bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) {return lhs.value < rhs.value;}template <typename T>bool operator>(const Modular<T> &lhs, const Modular<T> &rhs) {return lhs.value > rhs.value;}template <typename T>Modular<T> operator+(const Modular<T> &lhs, const Modular<T> &rhs) {return Modular<T>(lhs) += rhs;}template <typename T, typename U>Modular<T> operator+(const Modular<T> &lhs, U rhs) {return Modular<T>(lhs) += rhs;}template <typename T, typename U>Modular<T> operator+(U lhs, const Modular<T> &rhs) {return Modular<T>(lhs) += rhs;}template <typename T>Modular<T> operator-(const Modular<T> &lhs, const Modular<T> &rhs) {return Modular<T>(lhs) -= rhs;}template <typename T, typename U>Modular<T> operator-(const Modular<T> &lhs, U rhs) {return Modular<T>(lhs) -= rhs;}template <typename T, typename U>Modular<T> operator-(U lhs, const Modular<T> &rhs) {return Modular<T>(lhs) -= rhs;}template <typename T>Modular<T> operator*(const Modular<T> &lhs, const Modular<T> &rhs) {return Modular<T>(lhs) *= rhs;}template <typename T, typename U>Modular<T> operator*(const Modular<T> &lhs, U rhs) {return Modular<T>(lhs) *= rhs;}template <typename T, typename U>Modular<T> operator*(U lhs, const Modular<T> &rhs) {return Modular<T>(lhs) *= rhs;}template <typename T>Modular<T> operator/(const Modular<T> &lhs, const Modular<T> &rhs) {return Modular<T>(lhs) /= rhs;}template <typename T, typename U>Modular<T> operator/(const Modular<T> &lhs, U rhs) {return Modular<T>(lhs) /= rhs;}template <typename T, typename U>Modular<T> operator/(U lhs, const Modular<T> &rhs) {return Modular<T>(lhs) /= rhs;}template <typename T, typename U>Modular<T> power(const Modular<T> &a, const U &b) {assert(b >= 0);Modular<T> x = a, res = 1;U n = b;while (n > 0) {if (n & 1) res *= x;x *= x;n >>= 1;}return res;}template <typename T>std::istream &operator>>(std::istream &stream, Modular<T> &rhs) {typename common_type<typename Modular<T>::Type, int64_t>::type x;stream >> x;rhs = Modular<T>(x);return stream;}template <typename T>std::ostream &operator<<(std::ostream &stream, const Modular<T> &rhs) {stream << rhs.value;return stream;}constexpr int mod = 1000000007;using mint =Modular<std::integral_constant<std::decay<decltype(mod)>::type, mod>>;template <typename T>class Combination {private:vector<T> f, invf;public:Combination(int n) : f(n + 1, 1), invf(n + 1, 1) {for (int i = 1; i < n + 1; i++) {f[i] = f[i - 1] * i;}invf[n] /= f[n];for (int i = n; i > 0; i--) {invf[i - 1] = invf[i] * i;}}// nCrconst T operator()(int n, int r) const {if (r < 0 || n < r) return 0;return f[n] * invf[r] * invf[n - r];}};int main() {ios::sync_with_stdio(false);cin.tie(0);int N, M;cin >> N >> M;Combination<mint> comb(N);vector<mint> memo(M + 1, 0);for (int i = 1; i < M + 1; i++) {memo[i] = comb(M, i) * power(static_cast<mint>(i), N) - memo[i - 1];}cout << memo[M] << '\n';return 0;}