Submission #105373

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
105373	2019-04-11T14:53:11 Z	gs14004	Phibonacci (kriii2_P)	C++17	4 / 4	3 ms	628 KB

P

#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, 1);
	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);
	lint A = ans.first * ipow(pk.first, mod - 2) % mod;
	if(A == 0) A = ipow(pk.second, n - 1) * n % mod;
	cout << A << " " << (ans.second - pk.second * A % mod + mod) % mod << endl;
}

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);
                 ~^~~

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 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	1 ms	384 KB	Output is correct
8	Correct	3 ms	256 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Correct	3 ms	256 KB	Output is correct
13	Correct	2 ms	256 KB	Output is correct
14	Correct	3 ms	256 KB	Output is correct
15	Correct	3 ms	384 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	3 ms	384 KB	Output is correct
18	Correct	2 ms	256 KB	Output is correct
19	Correct	2 ms	256 KB	Output is correct
20	Correct	2 ms	256 KB	Output is correct

Subtask #2

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	3 ms	256 KB	Output is correct
6	Correct	3 ms	256 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	2 ms	256 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	0 ms	256 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	256 KB	Output is correct
18	Correct	3 ms	384 KB	Output is correct
19	Correct	3 ms	384 KB	Output is correct
20	Correct	3 ms	628 KB	Output is correct