Number Sequence

题目大意

HDU提交不了了，大家看看题吧就当娱乐一下
数列 类似于斐波那契的模7数列
f(1) = f(2) = 1
f(n) = (a * f(n - 1) + b * f(n - 2)) % 7


Time: 1000 ms
Memory: 32768 kB

解题思路及分析

题解是初学的时候写的，后来才发现这个是矩阵快速幂的板子，这里就懒得写了，说一下当时的思路
$1 <= n <= 100,000,000$

直接开数组会MLE 不开数组用三个数迭代模拟会TLE

规律题 因为后一项只与前两项有关，所以只要数组中有连续两项在前面出现过，后面就会重复数列前面的值，即周期数列

将相邻两个数组成一个二位数，只需要比较这个两位数是否出现过即可，由于每位有7种可能，共可以组成49个数字，即一个周期的最大值为50

需要注意的是，循环不一定是从头开始的（一开始找和开头两位相同的错了好几次……），因此后面的循环部分可能不包括开头的几个数字，故需要记录循环开始的位置

几组特殊取值

1. a = b = 1    为Fibonacci数列
2. (a + b) % 7 = 0    从第三项都是0   
3. a + b = 8    从第一项都是1 

AC代码

#include <bits/stdc++.h>
using namespace std;

int loop[100];
bool ap[100];	// 将相邻的两个数看成一个二位数标记出现
int pos[100];

int main()
{
    int n, a, b, T, flag, begin;
    while (~scanf("%d%d%d", &a, &b, &n) && (a || b || n))
    {
        memset(ap, false, sizeof(ap));
        memset(pos, 0, sizeof(pos));
        begin = 0;
        T = 0;
        flag = 0;
        loop[0] = 1;
        loop[1] = 1;
        ap[11] = true;
        for (int i = 2; i < n; i++)
        {
            loop[i] = (a * loop[i - 1] + b * loop[i - 2]) % 7;
            int x = loop[i - 1] * 10 + loop[i];
            if (ap[x])
            {
                begin = pos[x];
                T = i - begin - 1;
                flag = 1;
                break;
            }
            else 
            {
                ap[x] = true;
                pos[x] = i - 1;
            }
        }
        if (flag)
        {
            if (T == 1)
            {
                printf("%d\n", loop[begin]);
            }
            else
            {
                printf("%d\n", ((n - begin) % T == 0 ? loop[begin + T - 1] : loop[(n - begin) % T - 1 + begin]));
            }
        }
        else
        {
            printf("%d\n", loop[n - 1]);
        }
    }
    return 0;
}

题目反思及后续

再谈 HDU 1005 Number Sequence

网上有部分题解代码是错的，在此给出这篇博客，希望更多人可以看到。也不是去杠出题人和部分题解代码，不过追求完全正确答案总是正确的，探讨相关问题也有利于开拓思维。

虽然我说的错误代码能够AC，黑盒测试不可能涵盖所有可能的测试样例，但是还是希望大家在做题/做研究的时候能够保持严谨性

问题的发现

前几天一个学弟给我拿过来这样一份AC代码：

#include<iostream>
using namespace std;
int arr[10000];
int main()
{
	int a,b,c;
	arr[1]=arr[2]=1;
	while(cin>>a>>b>>c,a||b||c)
	{
		int i;
    	for( i=3;i<10000;i++)
    	{
            arr[i]=(a*arr[i-1]+b*arr[i-2])%7;
    	  	if(arr[i]==1&&arr[i-1]==1)
				break;
		}
		c=c%(i-2);
		arr[0]=arr[i-2];
		cout<<arr[c]<<endl;
	}
	return 0;
}

其实本来还有另外一段代码，他过来问我为啥一个AC了一个没有AC，其实两份代码几乎没有任何差别，只不过另外一份是用的函数返回值，这个直接break; 另外两份代码还有一点区别，这个是影响AC与否的重点：数组大小不一样。AC代码数组大小为1e5，WA代码的数组大小为1e4。

题干中的范围是1 <= n <= 100,000,000，开数组会直接MLE，是一道找循环节的规律思维题，而且在之前的博客中也提到过，循环起始位置+循环节长度不会超过50（算是半严格证明），所以和数组大小没关系。反而，由于循环不一定是从头开始，位置并不确定，（参考上一篇博客中的数据，(a + b) % 7 == 0的情况，从第三项开始均为0）这段代码反而会有问题

所以为什么他能AC呢？

问题的分析

先尝试找反例证明这段代码是错的，因为之前因为没有判断后面循环的情况WA了好几发，所以这次直接拿数据开始试，7 7 1、7 7 2 、7 7 3、7 7 10……结果发现都没有问题，所以还是要看代码

很容易发现这段代码算了前10000项， 直到找到循环节为止。（此处循环节是以11为循环起始，即从头开始）

但是刚刚的数据能够证明上述方式是错的，于是继续hack

优先试了10000以上的数据，发现基本都没有问题，直到我用了下面l俩组数据：

7 7 9999
7 7 10000

输出均为1。至此hack成功。

分析出现错误的原因

对于上面的特殊输入，循环从3开始不会找到1 1的组合，所以循环不会通过break跳出，而是一直执行到i==10000结束，此时i - 2 = 9998。

而后面的c = c % (i - 2)即对9998取余数，当c = 9999和c=10000时， c%(i-2)结果为1和2，即为输出前两项，即是该代码的问题所在。代码AC的原因可能是刚好后台数据没有对应的情况，对于该代码来说数据较弱。

问题的反思

由于黑盒测试局限性，出现有小问题但是AC了的代码是非常正常的。另外我从网上去查了一下该题的题解，发现很多代码都有问题。这道题其实数据非常水，甚至在循环节50左右就都没有进行必要的检查。

毕竟也是水题，其实没必要强求那么多。也不是去杠出题人和部分题解代码，不过追求完全正确答案总是正确的，探讨相关问题也有利于开拓思维。