# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
105354 |
2019-04-11T14:02:56 Z |
gs14004 |
Phibonacci (kriii2_P) |
C++17 |
|
3 ms |
512 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int mod = 1e9 + 7;
lint ipow(lint x, lint p){
lint ret = 1, piv = x;
while(p){
if(p & 1) ret = ret * piv % mod;
piv = piv * piv % mod;
p >>= 1;
}
return ret;
}
vector<int> berlekamp_massey(vector<int> x){
vector<int> ls, cur;
int lf, ld;
for(int i=0; i<x.size(); i++){
lint t = 0;
for(int j=0; j<cur.size(); j++){
t = (t + 1ll * x[i-j-1] * cur[j]) % mod;
}
if((t - x[i]) % mod == 0) continue;
if(cur.empty()){
cur.resize(i+1);
lf = i;
ld = (t - x[i]) % mod;
continue;
}
lint k = -(x[i] - t) * ipow(ld, mod - 2) % mod;
vector<int> c(i-lf-1);
c.push_back(k);
for(auto &j : ls) c.push_back(-j * k % mod);
if(c.size() < cur.size()) c.resize(cur.size());
for(int j=0; j<cur.size(); j++){
c[j] = (c[j] + cur[j]) % mod;
}
if(i-lf+(int)ls.size()>=(int)cur.size()){
tie(ls, lf, ld) = make_tuple(cur, i, (t - x[i]) % mod);
}
cur = c;
}
for(auto &i : cur) i = (i % mod + mod) % mod;
return cur;
}
int get_nth(vector<int> rec, vector<int> dp, lint n){
int m = rec.size();
vector<int> s(m), t(m);
s[0] = 1;
if(m != 1) t[1] = 1;
else t[0] = rec[0];
auto mul = [&rec](vector<int> v, vector<int> w){
int m = v.size();
vector<int> t(2 * m);
for(int j=0; j<m; j++){
for(int k=0; k<m; k++){
t[j+k] += 1ll * v[j] * w[k] % mod;
if(t[j+k] >= mod) t[j+k] -= mod;
}
}
for(int j=2*m-1; j>=m; j--){
for(int k=1; k<=m; k++){
t[j-k] += 1ll * t[j] * rec[k-1] % mod;
if(t[j-k] >= mod) t[j-k] -= mod;
}
}
t.resize(m);
return t;
};
while(n){
if(n & 1) s = mul(s, t);
t = mul(t, t);
n >>= 1;
}
lint ret = 0;
for(int i=0; i<m; i++) ret += 1ll * s[i] * dp[i] % mod;
return ret % mod;
}
int guess_nth_term(vector<int> x, lint n){
if(n < x.size()) return x[n];
vector<int> v = berlekamp_massey(x);
if(v.empty()) return 0;
return get_nth(v, x, n);
}
lint n, k;
pi dp[105];
int main(){
cin >> n >> k;
pi pn(0, 0);
pn.first = guess_nth_term({0, 1, 1, 2, 3, 5, 8, 13}, n);
if(n > 0) pn.second = guess_nth_term({0, 1, 1, 2, 3, 5, 8, 13}, n - 1);
dp[0] = pi(0, 1);
for(int i=1; i<69; i++){
lint x2 = dp[i-1].first * pn.first;
lint x1 = dp[i-1].first * pn.second + dp[i-1].second * pn.first;
lint x0 = dp[i-1].second * pn.second;
dp[i] = pi((x1 + x2) % mod, (x0 + x2) % mod);
}
vector<int> v1, v2;
for(int i=0; i<69; i++){
v1.push_back(dp[i].first);
v2.push_back(dp[i].second);
}
pi ans; // a pi + b
ans.first = guess_nth_term(v1, k);
ans.second = guess_nth_term(v2, k);
pi pk;; // a pi + b
pk.first = guess_nth_term({0, 1, 1, 2, 3, 5, 8, 13}, k);
pk.second = guess_nth_term({1, 0, 1, 1, 2, 3, 5, 8}, k);
if(pk.first == 0){
if(ans.first == 0) cout << "0 " << ans.second << endl;
else assert(0);
return 0;
}
else{
lint a = pk.first, b = pk.second, x = ans.first, y = ans.second;
cout << x * ipow(a, mod - 2) % mod << " " << (y - ((b * x % mod) * ipow(a, mod - 2) % mod) + mod) % mod << endl;
}
// (pk - b) / a = pi
}
Compilation message
P.cpp: In function 'std::vector<int> berlekamp_massey(std::vector<int>)':
P.cpp:20:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<x.size(); i++){
~^~~~~~~~~
P.cpp:22:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<cur.size(); j++){
~^~~~~~~~~~~
P.cpp:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<cur.size(); j++){
~^~~~~~~~~~~
P.cpp: In function 'int guess_nth_term(std::vector<int>, lint)':
P.cpp:82:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(n < x.size()) return x[n];
~~^~~~~~~~~~
P.cpp: In function 'std::vector<int> berlekamp_massey(std::vector<int>)':
P.cpp:32:30: warning: 'ld' may be used uninitialized in this function [-Wmaybe-uninitialized]
lint k = -(x[i] - t) * ipow(ld, mod - 2) % mod;
~~~~^~~~~~~~~~~~~
P.cpp:33:18: warning: 'lf' may be used uninitialized in this function [-Wmaybe-uninitialized]
vector<int> c(i-lf-1);
~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
256 KB |
Output is correct |
10 |
Correct |
2 ms |
256 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
256 KB |
Output is correct |
15 |
Correct |
3 ms |
256 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Correct |
3 ms |
332 KB |
Output is correct |
18 |
Correct |
3 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
256 KB |
Output is correct |
20 |
Correct |
3 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |