{"id":646,"date":"2021-11-27T17:15:50","date_gmt":"2021-11-27T09:15:50","guid":{"rendered":"https:\/\/blog.cauchyschwarz.com\/?p=646"},"modified":"2021-12-04T22:14:50","modified_gmt":"2021-12-04T14:14:50","slug":"fibonacci%e6%95%b0%e5%88%97%e5%bf%ab%e9%80%9f%e7%ae%97%e6%b3%95-2","status":"publish","type":"post","link":"https:\/\/blog.cauchyschwarz.com\/?p=646","title":{"rendered":"Fibonacci\u6570\u5217\u5feb\u901f\u7b97\u6cd5"},"content":{"rendered":"\n

\u901a\u8fc7fibonacci\u6570\u5217\u7684\u9012\u63a8\u516c\u5f0f\uff0c\u53ef\u4ee5\u5c06\u6c42\u6570\u5217\u8f6c\u6362\u4e3a\u6c42\u9012\u63a8\u77e9\u9635\u7684n\u6b21\u5e42\u3002<\/p>\n\n\n\n

\\begin{equation}
{\\left[ \\begin{array}{cc}
0 & 1 \\\\
1 & 1
\\end{array}
\\right ]}
\\times
{\\left[\\begin{array}{c}
f_{n} \\\\
f_{n+1}
\\end{array}
\\right]}
=
{\\left[\\begin{array}{c}
f_{n+1} \\\\
f_{n+2}
\\end{array}
\\right]}
\\end{equation}<\/p>\n\n\n\n

<\/p>\n\n\n\n

\u9898\u76ee<\/a><\/p>\n\n\n\n

#define MODULO (1000000000 + 7)\n\nstruct Matrix {\n    Matrix() {}\n    Matrix(int a00, int a01, int a10, int a11) {\n        v[0][0] = a00;\n        v[0][1] = a01;\n        v[1][0] = a10;\n        v[1][1] = a11;\n    }\n    long v[2][2];\n    void multiply(Matrix &other) {\n        Matrix res;\n        res.v[0][0] = (v[0][0] * other.v[0][0] + v[0][1] * other.v[1][0]) % MODULO;\n        res.v[0][1] = (v[0][0] * other.v[0][1] + v[0][1] * other.v[1][1]) % MODULO;\n        res.v[1][0] = (v[1][0] * other.v[0][0] + v[1][1] * other.v[1][0]) % MODULO;\n        res.v[1][1] = (v[1][0] * other.v[0][1] + v[1][1] * other.v[1][1]) % MODULO;\n        *this = res;\n    }\n};\n\n\/*\n * Complete the 'solve' function below.\n *\n * The function is expected to return an INTEGER.\n * The function accepts following parameters:\n *  1. INTEGER a\n *  2. INTEGER b\n *  3. INTEGER n\n *\/\n\nint solve(int a, int b, int n) {\n    Matrix I(0, 1, 1, 1);\n    Matrix res(1, 0, 0, 1);\n    while (n) {\n        if (n & 1) {\n            res.multiply(I);\n        }\n        n >>= 1;\n        I.multiply(I);\n    }\n    return (res.v[0][0] * a % MODULO + res.v[0][1] * b % MODULO) % MODULO;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u901a\u8fc7fibonacci\u6570\u5217\u7684\u9012\u63a8\u516c\u5f0f\uff0c\u53ef\u4ee5\u5c06\u6c42\u6570\u5217\u8f6c\u6362\u4e3a\u6c42\u9012\u63a8\u77e9\u9635\u7684n\u6b21\u5e42\u3002 \\begin{equation}{\\left[ \\begin{array}{cc}0 & 1 \\\\1 & ...<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[26],"class_list":["post-646","post","type-post","status-publish","format-standard","hentry","category-10","tag-algorithm"],"_links":{"self":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/646","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=646"}],"version-history":[{"count":12,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/646\/revisions"}],"predecessor-version":[{"id":1204,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/646\/revisions\/1204"}],"wp:attachment":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=646"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=646"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=646"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}