Submission #73467

#	Time	Username	Problem	Language	Result	Execution time	Memory
73467		duckmoon99	Fibonacci representations (CEOI18_fib)	C++14	5 / 100	4094 ms	544 KiB

fib

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e18
#define ret return

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const ll MOD = 1e9+7;

struct mat{
	ll a[2][2];
	void ini(ll a1, ll a2, ll a3, ll a4){
		a[0][0]=a1;
		a[0][1]=a2;
		a[1][0]=a3;
		a[1][1]=a4;
	}
};

ll add(ll a, ll b){
	ll res=(a+MOD)+(b+MOD);
	res%=MOD;
	ret res;
}

ll mult(ll a, ll b){
	ll res = (a+MOD)*b+(MOD);
	res%=MOD;
	ret res;
}

mat mat_mult(mat A, mat B){
	mat res;
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 2; j++){
			res.a[0][0]=add(mult(A.a[0][0],B.a[0][0]),mult(A.a[0][1],B.a[1][0]));
			res.a[0][1]=add(mult(A.a[0][0],B.a[0][1]),mult(A.a[0][1],B.a[1][1]));
			res.a[1][0]=add(mult(A.a[1][0],B.a[0][0]),mult(A.a[1][1],B.a[1][0]));
			res.a[1][1]=add(mult(A.a[1][0],B.a[0][1]),mult(A.a[1][1],B.a[1][1]));
		}
	}
	ret res;
}

ll a[111];

mat mat_exp(mat a, int n){
	if(n==1)ret a;
	if(n%2){
		mat res = mat_exp(a,n-1);
		ret mat_mult(res,a);
	}
	else{
		mat res = mat_exp(a,n/2);
		ret mat_mult(res,res);
	}
}

mat cur, r;

ll solve(ll p, int q){
	if(p==0){
		ret 1;
	}
	if(q==0){
		ret 0;
	}
	ll res = 0;
	for(int i = q; i >= 1; i--){
		if(mat_exp(r,i).a[0][0]<=p){
			res=add(res,solve(p-mat_exp(r,i).a[0][0],i-1));
		}
	}
	ret res;
}

int main(){
	int n;
	cin >> n;
	ll p=0;
	cur.ini(1,1,1,0);
	r=cur;
	int q = 1;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		p+=mat_exp(r,a[i]).a[0][0];
		while(mat_mult(cur,r).a[0][0]<=p){
			cur=mat_mult(cur,r);
			q++;
		}
		cout << solve(p,q) << endl;
	}

}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 15
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35