1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465 |
- #include <bits/stdc++.h>
-
- using namespace std;
- typedef long long LL;
- #define FOR(i, x, y) for (LL i = (x), _##i = (y); i < _##i; ++i)
- #define FORD(i, x, y) for (LL i = (x), _##i = (y); i > _##i; --i)
-
- struct Mat {
- static const int MOD = 10000;
- static const LL M = 2;
- LL v[M][M];
-
- Mat() { memset(v, 0, sizeof(v)); }
-
- void eye() { FOR(i, 0, M)v[i][i] = 1; }
-
- LL *operator[](LL x) { return v[x]; }
-
- const LL *operator[](LL x) const { return v[x]; }
-
- Mat operator*(const Mat &B) {
- const Mat &A = *this;
- Mat ret;
- FOR (k, 0, M)
- FOR (i, 0, M) if (A[i][k])
- FOR (j, 0, M)ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % MOD;
- return ret;
- }
-
- Mat pow(LL n) const {
- Mat A = *this, ret;
- ret.eye();
- for (; n; n >>= 1, A = A * A)
- if (n & 1) ret = ret * A;
- return ret;
- }
-
- Mat operator+(const Mat &B) {
- const Mat &A = *this;
- Mat ret;
- FOR (i, 0, M)FOR (j, 0, M)ret[i][j] = (A[i][j] + B[i][j]) % MOD;
- return ret;
- }
-
- void prt() const {
- FOR (i, 0, M)FOR (j, 0, M)printf("%lld%c", (*this)[i][j], j == M - 1 ? '\n' : ' ');
- }
- };
-
-
- int main() {
- Mat m;
- m[0][0] = m[0][1] = m[1][0] = 1;
- m[1][1] = 0;
-
- for (int n; cin >> n and n != -1;) {
- if (n == 0) {
- cout << 0 << endl;
- continue;
- }
- cout << m.pow(n - 1)[0][0] << endl;
- }
-
- return 0;
- }
|