結果
問題 | No.1035 Color Box |
ユーザー |
|
提出日時 | 2020-04-24 21:27:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 2,977 bytes |
コンパイル時間 | 1,068 ms |
コンパイル使用メモリ | 100,684 KB |
最終ジャッジ日時 | 2025-01-09 23:12:20 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <iostream>#include <algorithm>#include <map>#include <set>#include <queue>#include <stack>#include <numeric>#include <bitset>#include <cmath>static const int MOD = 1000000007;using ll = long long;using u32 = unsigned;using u64 = unsigned long long;using namespace std;template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;template<u32 M = 1000000007>struct modint{u32 val;modint(): val(0){}template<typename T>modint(T t){t %= (T)M; if(t < 0) t += (T)M; val = t;}modint pow(ll k) const {modint res(1), x(val);while(k){if(k&1) res *= x;x *= x;k >>= 1;}return res;}template<typename T>modint& operator=(T t){t %= (T)M; if(t < 0) t += (T)M; val = t; return *this;}modint inv() const {return pow(M-2);}modint& operator+=(modint a){val += a.val; if(val >= M) val -= M; return *this;}modint& operator-=(modint a){if(val < a.val) val += M-a.val; else val -= a.val; return *this;}modint& operator*=(modint a){val = (u64)val*a.val%M; return *this;}modint& operator/=(modint a){return (*this) *= a.inv();}modint operator+(modint a) const {return modint(val) +=a;}modint operator-(modint a) const {return modint(val) -=a;}modint operator*(modint a) const {return modint(val) *=a;}modint operator/(modint a) const {return modint(val) /=a;}modint operator-(){return modint(M-val);}bool operator==(const modint a) const {return val == a.val;}bool operator!=(const modint a) const {return val != a.val;}bool operator<(const modint a) const {return val < a.val;}};using mint = modint<MOD>;class Factorial {using mint = modint<MOD>;vector<mint> facts, factinv;public:explicit Factorial(int n) : facts(static_cast<u32>(n+1)), factinv(static_cast<u32>(n+1)) {facts[0] = 1;for (int i = 1; i < n+1; ++i) facts[i] = facts[i-1]*mint(i);factinv[n] = facts[n].inv();for (int i = n-1; i >= 0; --i) factinv[i] = factinv[i+1] * mint(i+1);}mint fact(int k) const {if(k >= 0) return facts[k]; else return factinv[-k];}mint operator[](const int &k) const {if(k >= 0) return facts[k]; else return factinv[-k];}mint C(int p, int q) const {if(q < 0 || p < q) return 0;return facts[p] * factinv[q] * factinv[p-q];}mint P(int p, int q) const {if(q < 0 || p < q) return 0;return facts[p] * factinv[p-q];}mint H(int p, int q) const {if(p < 0 || q < 0) return 0;return q == 0 ? 1 : C(p+q-1, q);}};using mint = modint<MOD>;int main() {int n, m;cin >> n >> m;Factorial f(n);mint ans = 0;for (int i = 0; i <= m; ++i) {if((m-i)&1) ans -= f.C(m, i)*(mint(i).pow(n));else ans += f.C(m, i)*(mint(i).pow(n));}cout << ans.val << "\n";return 0;}