結果
問題 | No.978 Fibonacci Convolution Easy |
ユーザー | tanimani364 |
提出日時 | 2020-02-06 12:54:10 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 4,297 bytes |
コンパイル時間 | 1,593 ms |
コンパイル使用メモリ | 143,100 KB |
実行使用メモリ | 18,916 KB |
最終ジャッジ日時 | 2024-09-25 06:44:36 |
合計ジャッジ時間 | 2,447 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 14 ms
9,300 KB |
testcase_02 | AC | 8 ms
6,944 KB |
testcase_03 | AC | 29 ms
18,092 KB |
testcase_04 | AC | 9 ms
6,944 KB |
testcase_05 | AC | 3 ms
6,940 KB |
testcase_06 | AC | 13 ms
8,388 KB |
testcase_07 | AC | 21 ms
12,748 KB |
testcase_08 | AC | 14 ms
9,868 KB |
testcase_09 | AC | 22 ms
14,424 KB |
testcase_10 | AC | 31 ms
18,916 KB |
testcase_11 | AC | 11 ms
7,684 KB |
testcase_12 | AC | 4 ms
6,940 KB |
testcase_13 | AC | 12 ms
8,428 KB |
testcase_14 | AC | 5 ms
6,940 KB |
testcase_15 | AC | 14 ms
9,176 KB |
testcase_16 | AC | 31 ms
18,768 KB |
testcase_17 | AC | 32 ms
18,764 KB |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 2 ms
6,940 KB |
ソースコード
#include<iostream> #include<string> #include<vector> #include<algorithm> #include<map> #include<set> #include<cstdio> #include<cmath> #include<deque> #include<numeric> #include<queue> #include<stack> #include<cstring> #include<limits> #include<functional> #include<unordered_set> #include<iomanip> #include<cassert> #include<regex> #include<bitset> #include<complex> #include<chrono> #define rep(i,a) for(int i=(int)0;i<(int)a;++i) #define pb push_back #define eb emplace_back using ll=long long; constexpr ll mod = 1e9 + 7; constexpr ll INF = 1LL << 60; template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } using namespace std; template <typename A, typename B> string to_string(pair<A, B> p); template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p); template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p); string to_string(const string& s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } string to_string(vector<bool> v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template <size_t N> string to_string(bitset<N> v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast<char>('0' + v[i]); } return res; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; } template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cerr << "\n"; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " <<to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif struct UF { vector<int>par;//親 vector<int>Rank;//木の深さ vector<int>sz;//要素数 UF(int n){init(n);} //初期化 void init(int n) { par.resize(n); Rank.resize(n);sz.resize(n); for (int i = 0; i < n; i++) { par[i]= i; Rank[i] = 0; sz[i]=1; } } //木の根を求める int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } //xとyの属する集合を併合 bool unite(int x, int y) { x = find(x); y = find(y); if (x == y)return false;//すでに同じ集合に属している if (Rank[x] < Rank[y]) {//高さが小さい方を下に par[x] = y; sz[y]+=sz[x]; } else { par[y] = x; if (Rank[x] == Rank[y])Rank[x]++;//同じだとrankが変わらないままになるので増やす(それ以外は大きい方のrankが採用される) sz[x]+=sz[y]; } return true; } //xとyが同じ集合に属するかを判定 bool same(int x, int y) { return find(x) == find(y); } int size(int k){//要素数を求める return sz[find(k)]; } }; void solve(){ ll n,p; cin>>n>>p; ll sum=0,ans=0; vector<ll>a(n); a[0]=0;a[1]=1; rep(i,n){ if(i>=2)a[i]=(p*a[i-1])%mod+a[i-2]%mod; a[i]%=mod; sum+=a[i]; sum%=mod; ans+=(sum*a[i])%mod; ans%=mod; } cout<<ans<<"\n"; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout<<fixed<<setprecision(15); solve(); return 0; }