1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
|
#include <cstring>
struct { long long a[3][3]; Matrix(bool unit) { memset(a, 0, sizeof (a)); if (unit) for (int i = 0; i < 3; i++) a[i][i] = 1; } long long &operator()(int i, int j) { return a[i][j]; } const long long &operator()(int i, int j) const { return a[i][j]; } #ifdef DBG void print() const { puts("Matrix is :"); for (int i = 0; i < 3; i++) { printf("( "); for (int j = 0; j < 3; j++) printf("%lld ", a[i][j]); printf(")n"); } } #endif } trans(false), f(false); long long n, m; long long mul(long long a, long long b) { long long res = 0; for (; b; b >>= 1, a = (a + a) % m) if (b & 1) res = (res + a) % m; return res; } Matrix operator*(const Matrix &a, const Matrix &b) { #ifdef DBG puts("Matrix multiply:"); a.print(); b.print(); #endif Matrix res(false); for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) for (int k = 0; k < 3; k++) (res(i, j) += mul(a(i, k), b(k, j))) %= m; #ifdef DBG res.print(); #endif return res; } Matrix pow(Matrix a, long long n) { #ifdef DBG printf("pow(trans, %lld)n", n); #endif Matrix res(true); for (; n; n >>= 1, a = a * a) if (n & 1) res = res * a; return res; } void initMatrix() { f(2, 0) = 1; trans(0, 1) = trans(0, 2) = trans(1, 1) = trans(1, 2) = trans(2, 2) = 1; } void calc(long long k, long long last) { trans(0, 0) = k % m; #ifdef DBG printf("calc(%lld, %lld)n", k, last); trans.print(); f.print(); #endif long long n = last - k / 10 + 1; f = pow(trans, n) * f; } int main() { scanf("%lld %lld", &n, &m); initMatrix(); long long k = 10; while (n >= k) { #ifdef DBG printf("k = %lldn", k); #endif calc(k, k - 1); k *= 10; } calc(k, n); printf("%lldn", f(0, 0)); return 0; }
|
近期评论