題目：

?

看起來比較難，范圍10^9 O（n）都過不了，但是僅僅是看起來。（雖然我WA了7次 TLE了3次，被自己蠢哭）

?

我們觀察到 0 <= f[i] <= 6 就簡單了，就像小學(xué)初中學(xué)的找到循環(huán)節(jié)然后求第n項(xiàng)。

?

我們只用記錄下兩個(gè)連續(xù)的數(shù)字重復(fù)出現(xiàn)，就找到了循環(huán)節(jié)，然后就簡單了。

?

注意：MOD函數(shù)是用于返回兩數(shù)相除的余數(shù)，返回結(jié)果的符號與除數(shù)（divisor）的符號相同。（來自百度百科） ，mod結(jié)果正負(fù)所以要與7正負(fù)相同。

?

代碼（詳細(xì)注釋）：

#include <bits\stdc++.h> using namespace std; typedef long long ll;int f[10000]; // 存遞推項(xiàng)。 int v[10][10]; // v[i][j]表示 f[k-1]和f[k]出現(xiàn)的位置，第二次出現(xiàn)就找到了循環(huán)節(jié)了。 int main() {int a,b,n;cin >> a >> b >> n;int round ; // 循環(huán)節(jié)長度f[1] = f[2] = 1;v[1][1] = 1; // 1，1連續(xù)出現(xiàn)的位置是1int start; // 循環(huán)節(jié)開始的位置-1。for(int i = 3;; i++){f[i] = ((a*f[i-1] + b*f[i-2])%7+7)%7; // 讓f[i]變成層正數(shù)。 // cout << "i: " << i << " f: " << f[i] << endl;if(i == n){cout << f[i] << endl; // 如果求出循環(huán)節(jié)之前求出了答案，直接輸出。return 0;}if(v[f[i-1]][f[i]] == 0){v[f[i-1]][f[i]] = i-1; // f[i-1],f[i]第一次出現(xiàn)}else{ // 第二次出現(xiàn)round = i-1-v[f[i-1]][f[i]]; // 循環(huán)節(jié)長度start = v[f[i-1]][f[i]]-1; // 循環(huán)節(jié)開始的位置-1。break;}}n -= start; // 減去不在循環(huán)節(jié)之內(nèi)的部分。n = n % round; // 求出n在循環(huán)節(jié)中的位置。//已知的循環(huán)節(jié)從 start+1 - start+round。if(n == 0) cout << f[start+round] << endl; else cout << f[start+n] << endl;return 0; } //written by zhangjiuding.

?

總結(jié)

以上是生活随笔為你收集整理的51nod 1126 求递推序列的第N项 思路：递推模拟，求循环节。详细注释的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。