結果
問題 | No.1181 Product Sum for All Subsets |
ユーザー |
![]() |
提出日時 | 2020-08-31 04:41:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 1,551 bytes |
コンパイル時間 | 1,834 ms |
コンパイル使用メモリ | 172,448 KB |
実行使用メモリ | 10,624 KB |
最終ジャッジ日時 | 2024-11-15 16:21:41 |
合計ジャッジ時間 | 3,530 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define fs first#define sc second#define pb push_back#define mp make_pair#define eb emplace_back#define ALL(A) A.begin(),A.end()#define RALL(A) A.rbegin(),A.rend()typedef long long LL;typedef pair<LL,LL> P;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<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}const LL mod=1000000007;const LL LINF=1LL<<62;const int INF=1<<30;int dx[]={1,0,-1,0,1,-1,1,-1};int dy[]={0,1,0,-1,1,-1,-1,1};int M_N = 400000;vector<LL> fact;vector<LL> inver(M_N+1);LL combi(int n,int r){if(n<r||n<0||r<0) return 0;return fact[n]%mod*inver[n-r]%mod*inver[r]%mod;}LL fpow(LL a, LL n){LL x = 1;while(n > 0){if(n&1){x=x*a%mod;}a=a*a%mod;n >>= 1;}return x;}void set_combi(){LL s=1;fact.push_back(1);for(int i=1;i<=M_N;i++){s*=i;s%=mod;fact.push_back(s);}inver[M_N]=fpow(fact[M_N],mod-2);for(int i=M_N-1;i>=0;i--){inver[i]=inver[i+1]*(i+1)%mod;}}int main(){set_combi();LL n, k;cin >> n >> k;k %= mod;LL S = k * (k + 1) %mod;S = S * fpow(2, mod - 2) %mod;LL ans = 0;for (LL i = 0; i < n; i++) {ans = (ans + fpow(S, i) * combi(n, i) %mod * fpow(k, n - i) %mod)%mod;}cout << ans << endl;return 0;}