結果
問題 | No.573 a^2[i] = a[i] |
ユーザー |
![]() |
提出日時 | 2017-10-06 23:12:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 120 ms / 2,000 ms |
コード長 | 1,922 bytes |
コンパイル時間 | 1,543 ms |
コンパイル使用メモリ | 169,416 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2024-11-17 01:55:00 |
合計ジャッジ時間 | 8,684 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define fst(t) std::get<0>(t) #define snd(t) std::get<1>(t) #define thd(t) std::get<2>(t) #define unless(p) if(!(p)) #define until(p) while(!(p)) using ll = long long; using P = std::tuple<int,int>; const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1}; ll N; template <typename T> T expt(T a, T n, T mod = std::numeric_limits<T>::max()){ T res = 1; while(n){ if(n & 1){res = res * a % mod;} a = a * a % mod; n >>= 1; } return res; } template <typename T> T inverse(T n, T mod){ return expt(n, mod-2, mod); } template <typename T> struct Combination{ T mod; std::vector<T> fact, inv; Combination() = default; Combination(int max_n, T mod) : mod(mod) { fact = std::vector<T>(max_n); inv = std::vector<T>(max_n); fact[0] = 1; inv[0] = 1; for(int i=1;i<max_n;i++){ fact[i] = fact[i-1] * i % mod; inv[i] = inverse(fact[i], mod); } } Combination(Combination const &) = default; Combination(Combination&&) = default; Combination& operator=(Combination const &) = default; Combination& operator=(Combination&&) = default; T nPr(T n, T r){ if(n < r){return 0;} return fact[n] * inv[r] % mod; } T nCk(T n, T k){ if(n < k){return 0;} return fact[n] * inv[k] % mod * inv[n-k] % mod; } T nHk(T n, T k){ if(n == 0 && k == 0){return 1;} return nCk(n+k-1, k); } }; const ll MOD = 1e9 + 7; Combination<ll> combination(200100, MOD); int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); std::cin >> N; ll res = 0ll; for(int i=1;i<=N;++i){ res = (res + combination.nCk(N, i) * expt<ll>(i, N - i, MOD) % MOD) % MOD; } std::cout << res << std::endl; }