結果
| 問題 | No.573 a^2[i] = a[i] |
| ユーザー |
 WA_TLE
|
| 提出日時 | 2017-10-06 22:50:40 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 27 ms / 2,000 ms |
| コード長 | 8,043 bytes |
| コンパイル時間 | 1,350 ms |
| コンパイル使用メモリ | 129,304 KB |
| 最終ジャッジ日時 | 2025-01-05 03:05:48 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 47 |
ソースコード
#include<deque>#include<queue>#include<vector>#include<algorithm>#include<iostream>#include<set>#include<cmath>#include<tuple>#include<string>#include<chrono>#include<functional>#include<iterator>#include<random>#include<unordered_set>#include<unordered_map>#include<array>#include<map>#include<iomanip>using namespace std;typedef long long int llint;typedef long double lldo;#define mp make_pair#define mt make_tuple#define pub push_back#define puf push_front#define pob pop_back#define pof pop_front#define fir first#define sec second#define res resize#define ins insert#define era erase#define dme cout<<-1<<endl;return 0//ios::sync_with_stdio(false);//<< setprecision(5)const int mod=1000000007;const long double big=1e9+10;const long double pai=3.141592653589793238462643383279502884197;const long double eps=1e-7;template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}llint lcm(llint a,llint b){return a/gcd(a,b)*b;}template<typename Arithmetic, typename Integral>std::enable_if_t< std::is_unsigned<Integral>::value, Arithmetic>ipow(Arithmetic bace, Integral n){//繰り返し二条法auto res = (Arithmetic)(1);while (n > 0) {if (n & 1) res *= bace;bace *= bace;n >>= 1;}return res;}template <uint64_t MOD> class mint_base;//mint_base_base型用の累乗関数template <uint64_t MOD> constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept;//mod計算を自動で行う整数テンプレートクラスtemplate <uint64_t MOD_ = 1000000007>class mint_base{public:static constexpr auto MOD = MOD_;static_assert(!(MOD <= 2), "MOD cannot be below 2.");static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしないstatic_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしないconstexpr mint_base<MOD> operator+(const mint_base<MOD> &other)const noexcept{auto v = *this;return v += other;}constexpr mint_base<MOD> operator-(const mint_base<MOD> &other)const noexcept{auto v = *this;return v -= other;}constexpr mint_base<MOD> operator*(const mint_base<MOD> &other)const noexcept{auto v = *this;return v *= other;}constexpr auto operator/(const mint_base<MOD> &other)const noexcept{auto v = *this;return v /= other;}constexpr mint_base<MOD>& operator+=(const mint_base<MOD> &other) noexcept{a += other.a;if (MOD <= a) { a -= MOD; };return *this;}constexpr mint_base<MOD>& operator-=(const mint_base<MOD> &other) noexcept{if (a >= other.a) {a -= other.a;}else {a = (a + MOD) - other.a;}return *this;}constexpr mint_base<MOD>& operator*=(const mint_base<MOD> &other) noexcept{#if 1a *= other.a;a %= MOD;#else//MOD <= (MAXUINT64 / 2)条件下uint64_t b = other.a, v = 0;while (b > 0) {if (b & 1) {v += a;if (v >= MOD)v -= MOD;}a += a;if (MOD <= a)a -= MOD;b >>= 1;}a = v;#endifreturn *this;}constexpr mint_base<MOD>& operator/=(const mint_base<MOD> &other) noexcept{return *this *= ~other;}constexpr mint_base<MOD> operator+()const noexcept { return *this; }constexpr mint_base<MOD> operator-()const noexcept{return{ MOD - a, mod_value_tag{} };}constexpr mint_base<MOD>& operator++() noexcept{if (MOD <= ++a) { a = 0; };return *this;}constexpr mint_base<MOD>& operator--() noexcept{if (a <= 0) { a = MOD; };--a;return *this;}constexpr mint_base<MOD> operator++(int) noexcept{auto tmp = *this;++*this;return tmp;}constexpr mint_base<MOD> operator--(int) noexcept{auto tmp = *this;--*this;return tmp;}constexpr mint_base<MOD> operator~()const noexcept{return ipow(*this, e_phi - 1);}constexpr mint_base<MOD>& operator=(const mint_base<MOD> &other) noexcept{a = other.a;return *this;}constexpr explicit operator uint64_t()const noexcept{return a;}constexpr explicit operator unsigned()const noexcept{return (unsigned)a;}static constexpr uint64_t getmod() noexcept{return MOD;}constexpr mint_base(uint64_t a_) noexcept :a(a_ % MOD) {}constexpr mint_base()noexcept : a(0) {}struct mod_value_tag {};constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {}private:static constexpr uint64_t get_e_phi()noexcept {//オイラー値の導出uint64_t temp = MOD;uint64_t m_ = MOD;for (uint64_t i = 2; i * i <= m_; ++i){if (m_ % i == 0){temp = temp / i * (i - 1);for (; m_ % i == 0; m_ /= i);}}if (m_ != 1)temp = temp / m_ * (m_ - 1);return temp;}static constexpr uint64_t e_phi = get_e_phi();//オイラー値uint64_t a;};//mint_base型用の累乗関数template<uint64_t MOD>constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept{mint_base<MOD> res = 1;while (n > 0){if (n & 1)res *= x;x *= x;n >>= 1;}return res;}//mint_baseの階乗計算//O(x)時間が必要のため、fact_set関数を推奨する。template<uint64_t MOD>constexpr mint_base<MOD> fact(mint_base<MOD> x)noexcept{mint_base<MOD> res(1);for (uint64_t i = 1; i <= (uint64_t)x; ++i){res *= i;}return res;}//mint_baseの階乗計算//0からxまでの階乗を返す//O(x)時間が必要template<uint64_t MOD>std::vector<mint_base<MOD>> fact_set(mint_base<MOD> x = mint_base<MOD>(-1)){mint_base<MOD> res(1);std::vector<mint_base<MOD>> set((uint64_t)(x)+1);set[0] = 1;for (uint64_t i = 1; i <= (uint64_t)x; ++i){res *= i;set[i] = res;}return set;}//mint_base型のstreamへの出力template<uint64_t MOD> std::ostream& operator<<(std::ostream& os, mint_base<MOD> i){os << (uint64_t)i;return os;}//mint_base型のstreamからの入力template<uint64_t MOD> std::istream& operator >> (std::istream& is, mint_base<MOD>& i){uint64_t tmp;is >> tmp;i = tmp;return is;}typedef mint_base<1000000007> mint;namespace mint_literal {constexpr mint operator""_mi(unsigned long long x)noexcept {return mint(x);}}using namespace mint_literal;//mint_baseの階乗計算//0からxまでの階乗を返す//O(N)template<int32_t X, uint64_t MOD = mint::MOD>/*constexpr*/ std::array<mint_base<MOD>, X + 1> fact_set_c(){mint_base<MOD> res(1);std::array<mint_base<MOD>, X + 1> set;set[0] = 1;for (int32_t i = 1; i <= X; ++i){res *= i;set[i] = res;}return set;}template<typename RET = mint, typename Integral>RET combination(Integral all, Integral get){assert(all >= get);get = std::min(all - get, get);#if 1//時間計算量O(logMOD)static const auto fact_v = fact_set_c<100001>();return fact_v[all] / (fact_v[get] * fact_v[all - get]);#elif 0//時間計算量O(1)//空間計算量、初期化時間計算量O(N^2)constexpr int32_t ALL_MAX = 10'000;static std::vector<RET> DP_comb[ALL_MAX + 1];if (!DP_comb[all].empty()){return DP_comb[all][get];}if (DP_comb[0].empty()){DP_comb[0].resize(1);DP_comb[0][0] = (RET)1;DP_comb[1].resize(1);DP_comb[1][0] = (RET)1;}for (int32_t i = 2; i <= all; i++){if (DP_comb[i].empty()){int32_t size = i / 2 + 1;DP_comb[i].resize(size);DP_comb[i][0] = (RET)1;for (int32_t j = 1; j < size - 1; j++){DP_comb[i][j] = DP_comb[i - 1][j - 1] + DP_comb[i - 1][j];}DP_comb[i][size - 1] = DP_comb[i - 1][size - 2] + DP_comb[i - 1][(i & 1) ? (size - 1) : (size - 2)];}}return DP_comb[all][get];#else//時間計算量O(get + logMOD)RET ret = (RET)1;for (Integral i = 1; i <= get; ++i){ret *= all + 1 - i;ret /= i;}return ret;#endif}int main(void){int n,m,h,i,j,k;//1,3,6//1,4,12,24cin>>n;auto fa=fact_set((mint_base<>)n+10);mint_base<> ans=0,gen=1;for(i=0;i<n;i++){ans+=fa[n]/(fa[n-i]*fa[i])*m_pow((mint_base<>)n-i,i);}cout<<ans<<endl;return 0;}