結果
問題 | No.1035 Color Box |
ユーザー |
![]() |
提出日時 | 2020-04-24 21:40:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 3,674 bytes |
コンパイル時間 | 2,504 ms |
コンパイル使用メモリ | 195,604 KB |
最終ジャッジ日時 | 2025-01-09 23:21:55 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>#define all(vec) vec.begin(), vec.end()#define pb push_back#define eb emplace_back#define fi first#define se secondusing namespace std;using ll = long long;using P = pair<ll, ll>;template <class T>using V = vector<T>;constexpr ll INF = (1LL << 30) - 1LL;constexpr ll MOD = 1000000007LL;constexpr int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};template <class T>void chmin(T &a, T b) { a = min(a, b); }template <class T>void chmax(T &a, T b) { a = max(a, b); }void debug() { cerr << "ok" << endl; }template <class T>void printv(const vector<T> &v) {for (int i = 0; i < v.size(); i++) cout << v[i] << (i + 1 == v.size() ? '\n' : ' ');}template <class T>void readv(vector<T> &v) {for (int i = 0; i < v.size(); i++) cin >> v[i];}//from http://noshi91.hatenablog.com/entry/2019/03/31/174006template <std::uint_fast64_t Modulus>class modint {using u64 = std::uint_fast64_t;public:u64 a;constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}constexpr u64 &value() noexcept { return a; }constexpr const u64 &value() const noexcept { return a; }constexpr modint operator+(const modint rhs) const noexcept {return modint(*this) += rhs;}constexpr modint operator-(const modint rhs) const noexcept {return modint(*this) -= rhs;}constexpr modint operator*(const modint rhs) const noexcept {return modint(*this) *= rhs;}constexpr modint operator/(const modint rhs) const noexcept {return modint(*this) /= rhs;}constexpr modint operator^(const u64 rhs) const noexcept {return modint(*this) ^= rhs;}constexpr modint &operator+=(const modint rhs) noexcept {a += rhs.a;if (a >= Modulus) {a -= Modulus;}return *this;}constexpr modint &operator-=(const modint rhs) noexcept {if (a < rhs.a) {a += Modulus;}a -= rhs.a;return *this;}constexpr modint &operator*=(const modint rhs) noexcept {a = a * rhs.a % Modulus;return *this;}constexpr modint &operator/=(modint rhs) noexcept {u64 exp = Modulus - 2;while (exp) {if (exp % 2) {*this *= rhs;}rhs *= rhs;exp /= 2;}return *this;}constexpr modint &operator^=(u64 exp) {modint rhs = modint(*this);a = 1;while (exp) {if (exp % 2) {*this *= rhs;}rhs *= rhs;exp /= 2;}return *this;}friend ostream &operator<<(ostream &os, const modint &x) {os << x.a;return os;}friend istream &operator>>(istream &is, modint &x) {is >> x.a;return is;}};using mint = modint<MOD>;vector<mint> f, fi;void comb(int n) {f.resize(n + 1);fi.resize(n + 1);f[0] = 1;for (ll i = 1; i <= n; i++) {f[i] = f[i - 1] * mint(i);}fi[n] = mint(1) / f[n];for (ll i = n - 1; i >= 0; i--) {fi[i] = fi[i + 1] * mint(i + 1LL);}}mint ncr(ll n, ll r) {if (n < r) {return mint(0);}if (r == 0) {return mint(1);}return f[n] * fi[n - r] * fi[r];}int main() {ios::sync_with_stdio(0);cin.tie(0);ll n, m;cin >> n >> m;comb(n + 10);mint res = 0;for (ll k = 0; k <= m; k++) {mint s = ncr(m, k);s *= mint(m - k) ^ n;if (k & 1) s *= mint(MOD - 1LL);res += s;}cout << res << endl;}