题目：传送门
解答：f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7
乍看之下像是递归。但是数据范围太大了，1定会超时。可以想到找规律。
如果将 f(n) 视为1个状态，那末决定它的是谁？是前两个状态。而且由于 mod 7，所以这个函数的定义域、值域都是{0,1,2,3,4,5,6}。
这样，我们可以构造1个 7*7的有限状态机（2维数组），每一个状态填写出现的次数。当我们行将填写1个状态时发现里面已出现了次数，当前次数 - 已有次数就是循环的范围。最多计算49次，我们1定会发现循环规律。
这里需要注意的是：
- 需要将输入的 n 减去刚刚发现规律时的状态机次数（正式开始循环），再对循环范围取模；
- 当取模 = 0时，应当加上循环范围。例如：1 1 4 2 4 2，如果直接依照取模计算，则 f(4) = 1 而不是 2；
- 无需判断 n 是不是小于循环范围，由于有限状态机1定停机。即便小于对循环范围取模仍得到自己。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main()
{
int a, b, i, j;
long n;
int map[7][7];
while (cin>>a>>b>>n && a && b && n)
{
if(n == 1 || n == 2)
{
cout<<"1"<<endl;
continue;
}
memset(map, 0, sizeof(map));
int val = 1;
map[1][1] = val;
i = 1;
j = (a*1 + b*1) % 7;
int k = 0;
while(!map[i][j])
{
val++;
map[i][j] = val;
int tmp = j;
j = (a*j + b*i) % 7;
i = tmp;
// 过剩操作，状态机1定会停机
//num--;
//if (num == 0)
//{
// cout<<j<<endl;
// break;
//}
}
int circle = (val + 1) - map[i][j];
int start = map[i][j];
n = (n - (start - 1)) % circle;;
if(n == 0) n = circle;
n = n + (start - 1);
int ans;
for (int k = 0; k < 7; k++)
{
for (int l = 0; l < 7; l++)
{
if (n == map[k][l])
{
ans = k;
}
}
}
cout<<ans<<endl;
continue;
}
return 0;
}