oj.uz

Submission #9271

# Submission time Handle Problem Language Result Execution time Memory
9271 2014-09-28T05:11:48 Z lemonsqueeze Phibonacci (kriii2_P) C++
1 / 4
 0 ms 1088 KB 
#include<stdio.h>

typedef long long ll;
const int MM = 1000000007;

struct Mat{
	ll d[2][2];
	Mat operator*(const Mat &l)const{
		Mat ans = {0};
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++){
				for(int k=0;k<2;k++){
					ans.d[i][j] += d[i][k]*l.d[k][j];
					ans.d[i][j] = (ans.d[i][j] % MM + MM ) % MM;
				}
			}
		}
		return ans;
	}
};

ll pw(ll a, ll b)
{
	ll ans = 1, mul = a;
	while( b > 0 ){
		if( b%2 == 1) ans *= mul;
		mul *= mul; b/=2;
		ans %= MM; mul %= MM;
	}
	return ans;
}

Mat Mpw(Mat a, ll b)
{
	Mat ans = {1,0,0,1}, mul = a;
	while( b > 0 ){
		if( b%2 == 1) ans = ans* mul;
		mul = mul* mul; b/=2;
	}
	return ans;
}

ll div(ll a){ return pw(a, MM-2); }


int main()
{
	ll N, K;
	scanf("%lld%lld", &N, &K);
	Mat dif = {1,1,1,0}, rev = {0,1,1,-1};
	Mat ans = Mpw( Mpw(dif, N), K), as = Mpw(dif, K-1);
	ans = ans * rev;
	ll Fnk_1 = ans.d[0][0], Fk_1 = as.d[0][0], Fnk_2 = ans.d[0][1], Fk_2 = as.d[0][1];
	ll A = Fnk_1 * div(Fk_1) % MM;
	ll B = ((Fnk_2 - Fk_2 * A ) %MM + MM) % MM;
	printf("%lld %lld", A, B);
	return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 0 ms 1088 KB Output is correct
3 Correct 0 ms 1088 KB Output is correct
4 Correct 0 ms 1088 KB Output is correct
5 Correct 0 ms 1088 KB Output is correct
6 Correct 0 ms 1088 KB Output is correct
7 Correct 0 ms 1088 KB Output is correct
8 Correct 0 ms 1088 KB Output is correct
9 Correct 0 ms 1088 KB Output is correct
10 Correct 0 ms 1088 KB Output is correct
11 Correct 0 ms 1088 KB Output is correct
12 Correct 0 ms 1088 KB Output is correct
13 Correct 0 ms 1088 KB Output is correct
14 Correct 0 ms 1088 KB Output is correct
15 Correct 0 ms 1088 KB Output is correct
16 Correct 0 ms 1088 KB Output is correct
17 Correct 0 ms 1088 KB Output is correct
18 Correct 0 ms 1088 KB Output is correct
19 Incorrect 0 ms 1088 KB Output isn't correct
20 Halted 0 ms 0 KB -