Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ifstream fin("bilean.in");
- ofstream fout("bilean.out");
- const int mod=301104;
- int N, i;
- int MAT[3][3], SOL[3][3];
- inline void mult(int A[][3], int B[][3], int C[][3])
- {
- int i, j, k;
- for (i = 0; i < 2; i++)
- for (j = 0; j < 2; j++)
- for (k = 0; k < 2; k++)
- C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % mod;
- }
- inline void lg_power(int P, int M[][3])
- {
- int C[3][3], AUX[3][3], i;
- memcpy(C, MAT, sizeof(MAT));
- M[0][0] = M[1][1] = 1;
- for (i = 0; (1 << i) <= P; i++)
- {
- if (P & (1 << i))
- {
- memset(AUX, 0, sizeof(AUX));
- mult(M, C, AUX);
- memcpy(M, AUX, sizeof(AUX));
- }
- memset(AUX, 0, sizeof(AUX));
- mult(C, C, AUX);
- memcpy(C, AUX, sizeof(C));
- }
- }
- int main()
- {
- fin>>N;
- if(N==1)
- fout<<2;
- else if(N==2)
- fout<<3;
- else
- {
- MAT[0][0] = 0; MAT[0][1] = 1; MAT[1][0] = 1; MAT[1][1] = 1;
- lg_power(N+1, SOL);
- fout<<SOL[1][1];
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement