結果
問題 | No.1035 Color Box |
ユーザー |
![]() |
提出日時 | 2022-09-13 20:54:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 3,481 bytes |
コンパイル時間 | 1,156 ms |
コンパイル使用メモリ | 137,136 KB |
最終ジャッジ日時 | 2025-02-07 04:50:33 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <iostream>#include <iomanip>#include <string>#include <vector>#include <cmath>#include <cstdlib>#include <algorithm>#include <ios>#include <iomanip>#include <queue>#include <numeric>#include <map>#include <set>#include <sstream>#include <bitset>#include <climits>#include <stack>#include <regex>#include <functional>#include <random>#ifdef _WIN64# include <atcoder/all>#endif#ifdef _MSC_VER# include <intrin.h># define __builtin_popcount __popcnt# define __builtin_popcountl __popcnt64#endifusing namespace std;#define ll long long#define rep(i, init, n) for(ll i = init; i < (ll)n; i++)#define rrep(i, init, n) for(ll i = init; i >= (ll)n; i--)#define all(x) (x).begin(), (x).end()#define sz(x) (ll)(x.size())#define Out(x) cout << x << endl#define Yes cout << "Yes" << endl#define No cout << "No" << endl#define Ans cout << ans << endl#define PI 3.14159265358979#define MOD 1000000007const int inf32 = INT_MAX / 2;const ll inf64 = 1LL << 60;template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }template<class T>bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }// -------------------------------------------------------------------------------------------------struct mint{ll x;mint(ll val = 0) { x = (val % MOD + MOD) % MOD; }mint operator-() const { return mint(-x); }mint& operator+=(const mint& other) { x += other.x; if (x >= MOD) x -= MOD; return *this; }mint& operator-=(const mint& other) { x -= other.x; if (x < 0) x += MOD; return *this; }mint& operator*=(const mint& other) { (x *= other.x) %= MOD; return *this; }mint& operator/=(const mint& other) { *this *= other.pow(MOD - 2); return *this; }mint operator+(const mint& other) const { return mint(*this) += other; }mint operator-(const mint& other) const { return mint(*this) -= other; }mint operator*(const mint& other) const { return mint(*this) *= other; }mint operator/(const mint& other) const { return mint(*this) /= other; }mint pow(ll i) const{mint ret = 1;for (mint tmp = x; i; tmp *= tmp, i >>= 1) if (i & 1) ret *= tmp;return ret;}friend ostream& operator<<(ostream& os, const mint& m) { os << m.x; return os; }};struct Combination{vector<ll> f, finv;bool precalc = false;Combination(ll n, bool calc_inv = false){f.resize(n + 1);if (calc_inv) finv.resize(n + 1), precalc = true;f[0] = 1;rep(i, 1, n + 1) f[i] = f[i - 1] * i % MOD;if (calc_inv) rep(i, 0, n + 1) finv[i] = mpow(f[i], MOD - 2);}ll mpow(ll x, ll y){if (y == 0) return 1;x %= MOD;if (x == 0) return 0;if (y % 2 == 0) return mpow(x * x % MOD, y / 2) % MOD;else return x * mpow(x, y - 1) % MOD;}ll P(ll x, ll y) { return precalc ? f[x] * finv[x - y] % MOD : f[x] * mpow(f[x - y], MOD - 2) % MOD; }ll C(ll x, ll y){ll a = f[x];ll b = precalc ? finv[y] * finv[x - y] % MOD : mpow(f[y] * f[x - y] % MOD, MOD - 2);return a * b % MOD;}ll H(ll x, ll y) { return C(x + y - 1, y); }};ll mpow(ll x, ll y){if (y == 0) return 1;x %= MOD;if (x == 0) return 0;if (y % 2 == 0) return mpow(x * x % MOD, y / 2) % MOD;else return x * mpow(x, y - 1) % MOD;}int main(){ll n, m; cin >> n >> m;Combination comb(100000, true);mint ans = mpow(m, n);rep(i, 1, m){mint tmp = (mint)comb.C(m, i) * mpow(i, n);ans += tmp * ((m - i) % 2 != 0 ? -1 : 1);}Ans;return 0;}