結果
問題 | No.978 Fibonacci Convolution Easy |
ユーザー | pazzle1230 |
提出日時 | 2020-01-31 21:34:21 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 4,636 bytes |
コンパイル時間 | 1,685 ms |
コンパイル使用メモリ | 170,412 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-18 20:51:37 |
合計ジャッジ時間 | 2,512 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,248 KB |
testcase_01 | AC | 8 ms
5,376 KB |
testcase_02 | AC | 5 ms
5,376 KB |
testcase_03 | AC | 16 ms
5,376 KB |
testcase_04 | AC | 6 ms
5,376 KB |
testcase_05 | AC | 3 ms
5,376 KB |
testcase_06 | AC | 7 ms
5,376 KB |
testcase_07 | AC | 11 ms
5,376 KB |
testcase_08 | AC | 9 ms
5,376 KB |
testcase_09 | AC | 12 ms
5,376 KB |
testcase_10 | AC | 16 ms
5,376 KB |
testcase_11 | AC | 7 ms
5,376 KB |
testcase_12 | AC | 3 ms
5,376 KB |
testcase_13 | AC | 7 ms
5,376 KB |
testcase_14 | AC | 4 ms
5,376 KB |
testcase_15 | AC | 8 ms
5,376 KB |
testcase_16 | AC | 16 ms
5,376 KB |
testcase_17 | AC | 16 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define INF_LL (int64)1e18 #define INF (int32)1e9 #define REP(i, n) for(int64 i = 0;i < (n);i++) #define FOR(i, a, b) for(int64 i = (a);i < (b);i++) #define all(x) x.begin(),x.end() #define fs first #define sc second using int32 = int_fast32_t; using uint32 = uint_fast32_t; using int64 = int_fast64_t; using uint64 = uint_fast64_t; using PII = pair<int32, int32>; using PLL = pair<int64, int64>; const double eps = 1e-10; template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;} template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;} template<typename T> vector<T> make_v(size_t a){return vector<T>(a);} template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts){ return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename U,typename... V> typename enable_if<is_same<T, U>::value!=0>::type fill_v(U &u,const V... v){u=U(v...);} template<typename T,typename U,typename... V> typename enable_if<is_same<T, U>::value==0>::type fill_v(U &u,const V... v){ for(auto &e:u) fill_v<T>(e,v...); } class UnionFind{ private: ::std::vector<int_fast32_t> par; size_t n; public: UnionFind(){} UnionFind(size_t n):n(n){ par.resize(n, -1); } uint_fast32_t find(uint_fast32_t x){ return par[x] < 0 ? x : par[x] = find(par[x]); } size_t size(uint_fast32_t x){ return -par[find(x)]; } bool unite(uint_fast32_t x, uint_fast32_t y){ x = find(x); y = find(y); if(x == y) return false; if(size(x) < size(y)) std::swap(x, y); par[x] += par[y]; par[y] = x; return true; } bool same(uint_fast32_t x, uint_fast32_t y){ return find(x) == find(y); } }; template<::std::uint_fast64_t mod> class ModInt{ private: using value_type = ::std::uint_fast64_t; value_type n; public: ModInt() : n(0) {} ModInt(value_type n_) : n(n_ % mod) {} ModInt(const ModInt& m) : n(m.n) {} template<typename T> explicit operator T() const { return static_cast<T>(n); } value_type get() const { return n; } friend ::std::ostream& operator<<(::std::ostream &os, const ModInt<mod> &a) { return os << a.n; } friend ::std::istream& operator>>(::std::istream &is, ModInt<mod> &a) { value_type x; is >> x; a = ModInt<mod>(x); return is; } bool operator==(const ModInt& m) const { return n == m.n; } bool operator!=(const ModInt& m) const { return n != m.n; } ModInt& operator*=(const ModInt& m){ n = n * m.n % mod; return *this; } ModInt pow(value_type b) const{ ModInt ans = 1, m = ModInt(*this); while(b){ if(b & 1) ans *= m; m *= m; b >>= 1; } return ans; } ModInt inv() const { return (*this).pow(mod-2); } ModInt& operator+=(const ModInt& m){ n += m.n; n = (n < mod ? n : n - mod); return *this; } ModInt& operator-=(const ModInt& m){ n += mod - m.n; n = (n < mod ? n : n - mod); return *this; } ModInt& operator/=(const ModInt& m){ *this *= m.inv(); return *this; } ModInt operator+(const ModInt& m) const { return ModInt(*this) += m; } ModInt operator-(const ModInt& m) const { return ModInt(*this) -= m; } ModInt operator*(const ModInt& m) const { return ModInt(*this) *= m; } ModInt operator/(const ModInt& m) const { return ModInt(*this) /= m; } ModInt& operator++(){ n += 1; return *this; } ModInt& operator--(){ n -= 1; return *this; } ModInt operator++(int){ ModInt old(n); n += 1; return old; } ModInt operator--(int){ ModInt old(n); n -= 1; return old; } ModInt operator-() const { return ModInt(mod-n); } }; template<::std::size_t size, ::std::uint_fast64_t mod=1000000007> class Factorial{ private: using value_type = ModInt<mod>; ::std::vector<value_type> fact, inv; public: Factorial() : fact(size+1, 1), inv(size+1, 1){ for(::std::size_t i = 1; i <= size; ++i){ fact[i] = fact[i-1] * value_type(i); inv[i] = fact[i].inv(); } } value_type comb(::std::int64_t a, ::std::int64_t b){ assert(a >= b); assert(b >= 0); return fact[a]*inv[b]*inv[a-b]; } value_type& operator[](::std::size_t k){ return fact[k]; } }; constexpr int64 mod = 1e9+7; using Mint = ModInt<mod>; Factorial<2020> f; int main(void) { cin.tie(0); ios::sync_with_stdio(false); Mint sum = 0; Mint a1 = 0, a2 = 1; int64 N, p; cin >> N >> p; if (N == 1) { cout << 0 << endl; return 0; } sum += a1 + a2; Mint sum2 = a1*a1+a2*a2; FOR(i, 2, N) { a1 = a2*p + a1; swap(a1, a2); sum += a2; sum2 += a2*a2; } cout << (sum*sum-sum2)/2 + sum2 << endl; }