| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 9606 |
2014-09-28T07:36:05 Z |
shashack |
Phibonacci (kriii2_P) |
C++ |
|
0 ms |
1680 KB |
#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <map>
#include <math.h>
#include <malloc.h>
#include <numeric>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#pragma warning(disable:4996)
#define REP(variable, repeatnumber) for(int variable=0; variable<(repeatnumber); ++variable)
#define FOR(variable, start, end) for(int variable=(start); variable<=(end); ++variable)
#define RFOR(variable, start, end) for(int variable=(start); variable>=(end); --variable)
#define ULL unsigned long long
#define LL long long
using namespace std; // 700B
typedef vector<LL> vec;
typedef vector<vec> mat;
int x,y,z;
const LL M = 1000000007;
LL n;
mat mul(mat &A, mat &B){
mat C(A.size(), vec(B[0].size()));
x = A.size();
for (int i = 0; i < x; i++){
y = B.size();
for (int k = 0; k < y; k++){
z = B[0].size();
for (int j = 0; j < z; j++){
C[i][j] = ((C[i][j] + A[i][k] * B[k][j])+ M) % M;
}
}
}
return C;
}
mat pow(mat A, LL n){
mat B(A.size(), vec(A.size()));
x = A.size();
for (int i = 0; i < x; i++){
B[i][i] = 1;
}
while (n>0){
if (n & 1) B = mul(B, A);
A = mul(A, A);
n >>= 1;
}
return B;
}
int main(){
mat A(2, vec(2));
A[0][0] = 1; A[0][1] = 1;
A[1][0] = 1; A[1][1] = 0;
cin >> n;
A = pow(A, n) ;
cout << A[1][0] << " ";
A[0][0] = 1; A[0][1] = 1;
A[1][0] = 1; A[1][1] = 0;
A = pow(A, n - 1) ;
cout << A[1][0] << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1680 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
