记录编号	424759	评测结果	AAAAAAAAAA
题目名称	01进制数	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2017-07-14 09:27:02	内存使用	0.31 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
 
#define MOD (15746)
 
inline void Pow(void);
 
int s[2][2] = {{0, 1},
               {1, 1}},
    res[2][2] = {{1, 0},
                 {0, 1}},
    fib[1][2] = {1, 1},
    ans[2][2];
int N;
 
int main() { 
#ifndef LOCAL
    freopen("binacy.in", "r", stdin);
    freopen("binacy.out", "w", stdout);
#endif
    scanf("%d", &N);
    Pow();
    for(int i = 0; i < 1; ++i) { 
        for(int j = 0; j < 2; ++j) { 
            for(int k = 0; k < 2; ++k) { 
                (ans[i][j] += fib[i][k] * res[k][j]) %= MOD;
            }
        }
    }
    printf("%d", ans[0][0]);
}
 
inline void Pow(void) { 
    int tmp[2][2];
    while(N) { 
        if(N & 1) { 
            memset(tmp, 0x00, sizeof(tmp));
            for(int i = 0; i < 2; ++i) { 
                for(int j = 0; j < 2; ++j) { 
                    for(int k = 0; k < 2; ++k) { 
                        (tmp[i][j] += res[i][k] * s[k][j]) %= MOD;
                    }
                }
            }
            for(int i = 0; i < 2; ++i) { 
                for(int j = 0; j < 2; ++j) { 
                    res[i][j] = tmp[i][j];
                }
            }
        }
        memset(tmp, 0x00, sizeof(tmp));
        for(int i = 0; i < 2; ++i) { 
            for(int j = 0; j < 2; ++j) { 
                for(int k = 0; k < 2; ++k) { 
                    (tmp[i][j] += s[i][k] * s[k][j]) %= MOD;
                }
            }
        }
        for(int i = 0; i < 2; ++i) { 
            for(int j = 0; j < 2; ++j) { 
                s[i][j] = tmp[i][j];
            }
        }
        N >>= 1;
    }
    return ;
}