結果
| 問題 | No.1181 Product Sum for All Subsets |
| ユーザー |
 micheeeeell1001
|
| 提出日時 | 2020-08-21 23:12:57 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 51 ms / 2,000 ms |
| コード長 | 6,627 bytes |
| コンパイル時間 | 2,392 ms |
| コンパイル使用メモリ | 198,276 KB |
| 最終ジャッジ日時 | 2025-01-13 06:34:31 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
ソースコード
#ifdef LOCAL#define _GLIBCXX_DEBUG#endif#include<bits/stdc++.h>using namespace std;#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)#define all(x) (x).begin(), (x).end()typedef long long ll;typedef long double ld;typedef pair<ll,ll> Pll;typedef vector<ll> vl;typedef vector<vl> vvl;typedef vector<vvl> vvvl;constexpr ll INF = numeric_limits<ll>::max()/4;constexpr ll n_max = 2e5+10;#define int lltemplate <typename A, typename B>string to_string(pair<A, B> p);string to_string(const string &s) {return '"' + s + '"';}string to_string(const char *c) {return to_string((string) c);}string to_string(bool b) {return (b ? "true" : "false");}template <size_t N>string to_string(bitset<N> v){string res = "";for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);return res;}template <typename A>string to_string(A v) {bool first = true;string res = "{";for(const auto &x : v) {if(!first) res += ", ";first = false;res += to_string(x);}res += "}";return res;}template <typename A, typename B>string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}void debug_out() {cerr << endl;}template<typename Head, typename... Tail>void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}#ifdef LOCAL#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#else#define debug(...) 42#endiftemplate<class T>bool chmax(T &a, T b){if(a < b){a = b; return true;} return false;}template<class T>bool chmin(T &a, T b){if(a > b){a = b; return true;} return false;}template<std::int_fast64_t Modulus>class modint {using i64 = int_fast64_t;public:i64 a;constexpr modint(const i64 x = 0) noexcept {this -> a = x % Modulus;if(a < 0){a += Modulus;}}constexpr int getmod() { return Modulus; }constexpr modint operator - () const noexcept {return a ? Modulus - a : 0;}constexpr const i64 &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 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 {i64 a_ = rhs.a, b = Modulus, u = 1, v = 0;while(b){i64 t = a_/b;a_ -= t * b; swap(a_,b);u -= t * v; swap(u,v);}a = a * u % Modulus;if(a < 0) a += Modulus;return *this;}// 自前実装constexpr bool operator==(const modint rhs) noexcept {return a == rhs.a;}constexpr bool operator!=(const modint rhs) noexcept {return a != rhs.a;}constexpr bool operator>(const modint rhs) noexcept {return a > rhs.a;}constexpr bool operator>=(const modint rhs) noexcept {return a >= rhs.a;}constexpr bool operator<(const modint rhs) noexcept {return a < rhs.a;}constexpr bool operator<=(const modint rhs) noexcept {return a <= rhs.a;}constexpr modint& operator++() noexcept {return (*this) += modint(1);}// constexpr modint operator++(int) {// modint tmp(*this);// operator++();// return tmp;// }constexpr modint& operator--() noexcept {return (*this) -= modint(1);}// constexpr modint operator--(int) {// modint tmp(*this);// operator--();// return tmp;// }template<typename T>friend constexpr modint modpow(const modint &mt, T n) noexcept {if(n < 0){modint t = (modint(1) / mt);return modpow(t, -n);}modint res = 1, tmp = mt;while(n){if(n & 1)res *= tmp;tmp *= tmp;n /= 2;}return res;}friend constexpr string to_string(const modint &mt) noexcept {return to_string(mt.a);}};// 標準入出力対応template<std::int_fast64_t Modulus>std::ostream &operator<<(std::ostream &out, const modint<Modulus> &m) {out << m.a;return out;}template<std::int_fast64_t Modulus>std::istream &operator>>(std::istream &in, modint<Modulus> &m) {ll a;in >> a;m = modint<Modulus>(a);return in;}const ll MOD = 1e9+7;// const ll MOD = 998244353;using mint = modint<MOD>;template<class T> struct BiCoef {vector<T> fact_, inv_, finv_;constexpr BiCoef() {}constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {init(n);}constexpr void init(int n) noexcept {fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);int MOD = fact_[0].getmod();for(int i = 2; i < n; i++){fact_[i] = fact_[i-1] * i;inv_[i] = -inv_[MOD%i] * (MOD/i);finv_[i] = finv_[i-1] * inv_[i];}}constexpr T com(int n, int k) const noexcept {if (n < k || n < 0 || k < 0) return 0;return fact_[n] * finv_[k] * finv_[n-k];}constexpr T fact(int n) const noexcept {if (n < 0) return 0;return fact_[n];}constexpr T inv(int n) const noexcept {if (n < 0) return 0;return inv_[n];}constexpr T finv(int n) const noexcept {if (n < 0) return 0;return finv_[n];}};BiCoef<mint> bc(n_max);signed main(){cin.tie(nullptr);ios::sync_with_stdio(false);ll n; cin >> n;ll k; cin >> k;mint ans = 0;mint sum = (mint(1) + mint(k)) * mint(k) / mint(2);rep(i,0,n){ans += bc.com(n, i) * modpow(sum, i) * modpow(mint(k), n - i);}cout << ans << "\n";}