結果
問題 | No.1181 Product Sum for All Subsets |
ユーザー |
|
提出日時 | 2020-08-22 01:15:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 2,161 bytes |
コンパイル時間 | 872 ms |
コンパイル使用メモリ | 84,856 KB |
実行使用メモリ | 9,472 KB |
最終ジャッジ日時 | 2024-10-15 06:38:24 |
合計ジャッジ時間 | 2,251 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include<iostream>#include<string>#include<iomanip>#include<cmath>#include<vector>#include<algorithm>#include<utility>using namespace std;#define int long long#define endl "\n"constexpr long long INF = (long long)1e18;constexpr long long MOD = 1'000'000'007;struct fast_io {fast_io(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);};} fio;class binomial_coefficients {long long MAX_VAL;vector<long long> fac, mmi;public:binomial_coefficients(){}binomial_coefficients(long long num){init(num);}~binomial_coefficients(){}void init(long long num){MAX_VAL = num+1;fac.resize(MAX_VAL);mmi.resize(MAX_VAL);factorial_mod();modular_multiplicatibe_inverse();}void factorial_mod(){fac[0] = 1;for(long long i = 1; i < MAX_VAL; fac[i] %= MOD, i++)fac[i] = fac[i - 1] * (i % MOD);}long long power(long long x, long long n){long long ans = 1;for(;n;n >>= 1, x *= x, ans %= MOD, x %= MOD)if(n&1)ans*=x;return ans % MOD;}void exgcd(long long a, long long b, long long &x, long long &y){if(b == 0){x = 1;y = 0;return ;}exgcd(b, a % b, y, x);y -= a / b * x;}void modular_multiplicatibe_inverse(){long long x, y;exgcd(fac[MAX_VAL - 1], MOD, x, y);mmi[MAX_VAL-1] = (x%MOD + MOD) % MOD;// mmi[MAX_VAL-1] = power(fac[MAX_VAL-1], MOD-2);for(long long i = MAX_VAL - 2; i >= 0; mmi[i]%=MOD, i--)mmi[i] = mmi[i + 1] * ((i + 1) % MOD);}long long combination(long long n, long long r){return n < r ? 0 :fac[n] * (mmi[r] * mmi[n-r] % MOD) % MOD;}};signed main(){cout<<fixed<<setprecision(10);binomial_coefficients BC;int N, K;int S;int ans = 0;cin>>N>>K;K %= MOD;BC.init(N * 2);ans = BC.power(K % MOD, N);ans %= MOD;S = (K % MOD) * ((K + 1) % MOD) % MOD * BC.power(2, MOD-2) % MOD;S %= MOD;for(int i = 1; i < N; i++){ans += (((BC.combination(N, i) % MOD) * (BC.power(S, i) % MOD)) % MOD * BC.power(K, N - i) % MOD) % MOD;ans %= MOD;}cout<<ans<<endl;return 0;}