终于结束的起点（滚动数组，记忆化搜索）

任意门

终于结束的起点

题目背景

终于结束的起点
终于写下句点
终于我们告别
终于我们又回到原点
……

一个个 OIer 的竞赛生涯总是从一场 NOIp 开始，大多也在一场 NOIp 中结束，好似一次次轮回在不断上演。
如果这次 NOIp 是你的起点，那么祝你的 OI 生涯如同夏花般绚烂。
如果这次 NOIp 是你的终点，那么祝你的 OI 回忆宛若繁星般璀璨。
也许这是你最后一次在洛谷上打比赛，也许不是。
不过，无论如何，祝你在一周后的比赛里，好运。

当然，这道题也和轮回有关系。

题目描述

广为人知的斐波拉契数列 $\mathrm{fib}(n)$ 是这么计算的

也就是 $0,1,1,2,3,5,8,13\cdots$，每一项都是前两项之和。

小 F 发现，如果把斐波拉契数列的每一项对任意大于 $1$ 的正整数 $M$ 取模的时候，数列都会产生循环。

当然，小 F 很快就明白了，因为 ($\mathrm{fib}(n-1)\mathrm{mod}M$) 和 ($\mathrm{fib}(n-2)\mathrm{mod}M)$ 最多只有 $M^2$ 种取值，所以在 $M^2$ 次计算后一定出现过循环。

甚至更一般地，我们可以证明，无论取什么模数 $M$，最终模 $M$ 下的斐波拉契数列都会是 $0,1,\cdots ,0,1,\cdots$。

现在，给你一个模数 $M$，请你求出最小的 $n>0$，使得 $\mathrm{fib}(n)\mathrm{mod}M=0,\mathrm{fib}(n+1)\mathrm{mod}M=1$。

输入格式

输入一行一个正整数 $M$。

输出格式

输出一行一个正整数 $n$。

样例 #1

样例输入 #1

2
1

样例输出 #1

3
1

样例 #2

样例输入 #2

6
1

样例输出 #2

24
1

提示

样例 1 解释

斐波拉契数列为 $0,1,1,2,3,5,8,13,21,34,\cdots$，在对 $2$ 取模后结果为 $0,1,1,0,1,1,0,1,1,0,\cdots$。

我们可以发现，当 $n=3$ 时，$f(n)\mathrm{mod}2=0,f(n+1)\mathrm{mod}2=1$，也就是我们要求的 $n$ 的最小值。

数据范围

对于 $30\%$ 的数据，$M\le 18$；

对于 $70\%$ 的数据，$M\le 2018$；

对于 $100\%$ 的数据，$2\le M\le 706150=$0xAC666。

提示

如果你还不知道什么是取模 $(\mathrm{mod})$，那我也很乐意告诉你，模运算是求整数除法得到的余数，也就是竖式除法最终「除不尽」的部分，也即
$$a\mathrm{mod}M=k⟺a=bM+k(M>0,0\le k<M)$$
其中 $a,b,k$ 都是非负整数。

如果你使用 C / C++，你可以使用 % 来进行模运算。

如果你使用 Pascal，你可以使用 mod 来进行模运算。

这道题目，很容易RE，一个是要取模再做，不然容易RE，再是告诉了你m的大小，但是你并不能确定n的最小大小，万一是m*m的话，那数组就会爆炸，最好的方法是用滚动数组。当然也可以记忆化搜索，这样子就只用递归，而不使用空间了。

我的错误做法：

只拿了80分，是因为最后两个测试样例RE了，应该是n可能会很大。

#include

using namespace std;

const int N=706155;
int f[N];
int m;

void fib()
{
    for(int i=2;i<N;i++)
        f[i]=(f[i-1]+f[i-2])%m;
}


int main()
{
    scanf("%d",&m);
    f[0]=0,f[1]=1;
    fib();
    for(int i=1;i<m*m;i++)
    {
        if(f[i]==0&&f[i+1]==1)
        {printf("%d",i);return 0;}
    }

    return 0;
}

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

解法一—记忆化搜索正解：

#include
typedef long long ll;
using namespace std;
const ll INF=0x7fffffff;
ll fp[10000002];//记忆数组，虽然m不大但是不知道n多大，尽量开大，不过1千万差不多极限
ll m;
ll f(ll i)
{
    if(fp[i])return fp[i];//调取记忆
    if(i==1||i==2)return fp[i]=1%m;
    else return fp[i]=(f(i-1)+f(i-2))%m;//这时就顺带%m可以使主程序更简单
}
int main()
{
    scanf("%lld",&m);
    ll i=1;//枚举
    while(f(i)!=0||f(i+1)!=1)//题目要求
    {
        i++;
    }
    printf("%lld",i);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

解法二—滚动数组

因为我们每次只考虑这两个数是否满足我们的要求，然后这两个数与推出下一个数有关，所以我们最好就是用滚动数组来保存这三个数即可。

#include
#include
using namespace std;
int fi[5],m;
int main()
{
    scanf("%d",&m);
    fi[1]=0; fi[2]=1;
    for(int i=1;;i++)
    {
        fi[3]=(fi[1]+fi[2])%m;
        if(fi[2]==0&&fi[3]==1)
        {
            printf("%d\n",i);
            return 0;
        }
        fi[1]=fi[2]; fi[2]=fi[3];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19