結果
問題 |
No.1181 Product Sum for All Subsets
|
ユーザー |
👑 ![]() |
提出日時 | 2020-10-24 18:44:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,335 bytes |
コンパイル時間 | 1,547 ms |
コンパイル使用メモリ | 168,468 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-21 15:26:02 |
合計ジャッジ時間 | 2,688 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include<bits/stdc++.h> using namespace std; using LL = long long; using ULL = unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) template<ULL M> struct modint { ULL x; modint(ULL val = 0) : x(val) {} modint& operator+=(modint r) { x += r.x; if (x >= M) x -= M; return *this; } modint operator+(modint r) const { modint res = x; return res += r; } modint& operator-=(modint r) { x += M - r.x; if (x >= M) x -= M; return *this; } modint operator-(modint r) const { modint res = x; return res -= r; } modint& operator*=(modint r) { x = x * r.x % M; return *this; } modint operator*(modint r) const { return modint(x * r.x % M); } modint pow(ULL r) const { if (r == 0) return modint(1); modint res = pow(r / 2); res *= res; if (r % 2) res *= *this; return res; } modint& operator/=(modint r) { *this *= r ^ (M - 1); return *this; } modint operator/(modint r) const { return *this * (r.pow(M - 2)); } ULL& operator*() { return x; } const ULL& operator*() const { return x; } }; const ULL M = 1000000007; using MLL = modint<M>; int main() { ULL N, K; cin >> N >> K; MLL mK = K % M; MLL ans = 0; ans += (mK * (mK + 3) / 2).pow(N); ans -= (mK * (mK + 1) / 2).pow(N); cout << *ans << endl; return 0; }