結果
問題 | No.1181 Product Sum for All Subsets |
ユーザー |
![]() |
提出日時 | 2020-08-21 22:28:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 105 ms / 2,000 ms |
コード長 | 2,978 bytes |
コンパイル時間 | 859 ms |
コンパイル使用メモリ | 89,836 KB |
実行使用メモリ | 6,400 KB |
最終ジャッジ日時 | 2024-10-15 05:56:18 |
合計ジャッジ時間 | 2,845 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <cstdio>#include <cstdlib>#include <cmath>#include <cassert>#include <algorithm>#include <functional>#include <iostream>#include <map>#include <numeric>#include <queue>#include <set>#include <stack>#include <string>#include <tuple>#include <vector>#define repi(i,a,b) for(ll i=(a);i<(b);++i)#define rep(i,a) repi(i,0,a)#define repdi(i,a,b) for(ll i=(a)-1;i>=(b);--i)#define repd(i,a) repdi(i,a,0)#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )#define all(a) (a).begin(), (a).end()#define rall(a) (a).rbegin(), (a).rend()#define endl '\n'#define debug(x) std::cerr << #x << " = " << (x) << endl;using ll = long long;using P = std::pair<ll, ll>;constexpr ll INF = 1ll<<60;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }template<class S, class T>std::ostream& operator<< ( std::ostream& out, const std::pair<S,T>& a ){ std::cout << '(' << a.first << ", " << a.second << ')'; return out; }template<class T>std::ostream &operator<< ( std::ostream& out, const std::vector<T>& a ){ std::cout << '['; rep( i, a.size() ){ std::cout << a[i]; if( i != a.size()-1 ) std::cout << ", "; } std::cout << ']'; return out; }const ll mod = 1000000007;struct mint {ll x; // typedef long long ll;mint(ll x=0):x((x%mod+mod)%mod){}mint operator-() const { return mint(-x);}mint& operator+=(const mint a) {if ((x += a.x) >= mod) x -= mod;return *this;}mint& operator-=(const mint a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}mint& operator*=(const mint a) {(x *= a.x) %= mod;return *this;}mint operator+(const mint a) const {mint res(*this);return res+=a;}mint operator-(const mint a) const {mint res(*this);return res-=a;}mint operator*(const mint a) const {mint res(*this);return res*=a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}// for prime modmint inv() const {return pow(mod-2);}mint& operator/=(const mint a) {return (*this) *= a.inv();}mint operator/(const mint a) const {mint res(*this);return res/=a;}};struct combination {std::vector<mint> fact, ifact;combination(int n):fact(n+1),ifact(n+1) {assert(n < mod);fact[0] = 1;for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;ifact[n] = fact[n].inv();for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;}mint operator()(int n, int k) {if (k < 0 || k > n) return 0;return fact[n]*ifact[k]*ifact[n-k];}};ll N, K;combination comb( 200010 );int main() {std::cin >> N >> K;mint S = mint(K)*(K+1)/2;mint ans = 0;rep( i, N ) {ans += comb( N, i )*S.pow(i)*mint(K).pow(N-i);}std::cout << ans.x << endl;return 0;}