題目

斐波那契數列大家都非常熟悉。它的定義是：f(x) = 1 .... (x=1,2) f(x) = f(x-1) + f(x-2) .... (x>2)對于給定的整數 n 和 m，我們希望求出： f(1) + f(2) + ... + f(n) 的值。但這個值可能非常大，所以我們把它對 f(m) 取模。 公式參見【圖1.png】但這個數字依然很大，所以需要再對 mod 求模。

【數據格式】

輸入為一行用空格分開的整數 n m mod (0 < n, m, mod < 10^18)
輸出為1個整數

例如，如果輸入：
2 3 5
程序應該輸出：
0

再例如，輸入：
15 11 29
程序應該輸出：
25

資源約定：
峰值內存消耗 < 256M
CPU消耗 < 1000ms

請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內容。

所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。

注意: main函數需要返回0
注意: 只使用ANSI C/ANSI C++ 標準，不要調用依賴于編譯環境或操作系統的特殊函數。
注意: 所有依賴的函數必須明確地在源文件中 #include < xxx>， 不能通過工程設置而省略常用頭文件。

提交時，注意選擇所期望的編譯器類型。

代碼

#include <iostream> #include <algorithm> #include <cstring>using namespace std;typedef unsigned long long LL;LL n, m, mod;class M { public:LL data[2][2];M() { memset(data, 0, sizeof(data)); } };void solve1() {LL a = 1;LL b = 1;if (m >= n + 2) {for (LL i = 3; i <= n + 2; ++i) {LL t = a;a = b;b += t;}printf("%llu\n", b % mod - 1);} else {//m<n+2LL fibM, fibN_2 = 0;for (LL i = 3; i <= n + 2; ++i) {LL t = a;a = b;b += t;if (i == m) fibM = b;}fibN_2 = b;printf("%llu %llu\n", fibN_2, fibN_2 % fibM % mod - 1);}}//將兩個2*2的矩陣相乘 M *mul(M *m1, M *m2) {M *ans = new M();ans->data[0][0] = m1->data[0][0] * m2->data[0][0] + m1->data[0][1] * m2->data[1][0];ans->data[0][1] = m1->data[0][0] * m2->data[0][1] + m1->data[0][1] * m2->data[1][1];ans->data[1][0] = m1->data[1][0] * m2->data[0][0] + m1->data[1][1] * m2->data[1][0];ans->data[1][1] = m1->data[1][0] * m2->data[0][1] + m1->data[1][1] * m2->data[1][1];return ans; }//快速乘法 LL mm(LL a, LL b, LL mod) {if (a > b) {LL t = a;a = b;b = t;}LL x = 0;while (b != 0) {if ((b & 1) == 1) {x = (x + a) % mod;}a = (a * 2) % mod;b >>= 1;}return x; }//將兩個2*2的矩陣相乘 M *mul(M *m1, M *m2, LL mod) {M *ans = new M();ans->data[0][0] = (mm(m1->data[0][0], m2->data[0][0], mod) + mm(m1->data[0][1], m2->data[1][0], mod)) % mod;ans->data[0][1] = (mm(m1->data[0][0], m2->data[0][1], mod) + mm(m1->data[0][1], m2->data[1][1], mod)) % mod;ans->data[1][0] = (mm(m1->data[1][0], m2->data[0][0], mod) + mm(m1->data[1][1], m2->data[1][0], mod)) % mod;ans->data[1][1] = (mm(m1->data[1][0], m2->data[0][1], mod) + mm(m1->data[1][1], m2->data[1][1], mod)) % mod;return ans; }//m的n次冪log(n) M *mPow(M *m, LL n) {M *E = new M();//單位矩陣E->data[0][0] = 1;E->data[1][1] = 1;while (n != 0) {if (n & 1 == 1) {E = mul(E, m);}m = mul(m, m);//按平方倍增n >>= 1;}return E; }//m的n次冪log(n) M *mPow(M *m, LL n, LL mod) {M *E = new M();//單位矩陣E->data[0][0] = 1;E->data[1][1] = 1;while (n != 0) {if ((n & 1) == 1) {E = mul(E, m, mod);}m = mul(m, m, mod);//按平方倍增n >>= 1;}return E; }LL fib(LL i) {//[1,1]B^(i-2)M *A = new M();A->data[0][0] = 1;A->data[0][1] = 1;M *B = new M();B->data[0][0] = 1;B->data[0][1] = 1;B->data[1][0] = 1;M *ans = mul(A, mPow(B, i - 2));return ans->data[0][0]; }LL fib(LL i, LL mod) {//[1,1]B^(i-2)M *A = new M();A->data[0][0] = 1;A->data[0][1] = 1;M *B = new M();B->data[0][0] = 1;B->data[0][1] = 1;B->data[1][0] = 1;M *ans = mul(A, mPow(B, i - 2, mod), mod);return ans->data[0][0]; }void solve2() {if (m >= n + 2) {printf("%llu\n", fib(n + 2, mod) - 1);} else {//m<n+2LL fibm = fib(m);printf("%llu\n", fib(n + 2, fibm) % mod - 1);} }int main(int argc, const char *argv[]) {scanf("%llu %llu %llu", &n, &m, &mod); // solve1(); // for (int i = 3; i <= 10; ++i) { // cout<< fib(i)<<endl; // }solve2(); //cout<<mm(3,7,5);return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的征战蓝桥 —— 2014年第五届 —— C/C++A组第9题——斐波那契的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。