hihocoder1239分析

一、题意分析

给定一个n个数的数列，求其中的前缀斐波那契子串的个数对1000000007取模的值。例如：对于数列a{a1~a6}：
2 1 1 2 2 3

{a2}: 1
{a3}: 1
{a2, a3}: 1 1
{a2, a3, a4}: 1 1 2
{a2, a3, a5}: 1 1 2
{a2, a3, a4, a6}: 1 1 2 3
{a2, a3, a5, a6}: 1 1 2 3
有7个前缀斐波那契子串，解为7。

n<=1000000, 0<=ai<=100000

二、算法分析：

第一反应是动态规划。但是看到n的范围达到了10^{6，感觉有点怕MLE。后来看到了ai的范围是10}5。而fibonacci数列第25项为75025，10^6*25的int数组还是可以开下的。

所以就定义转移方程如下：

f(i, j)表示当前在从ai取到an，当前正在取的是fibonacci数列的第j位。f(0, 0)即为所求。

当a[i] = fibonacci[j]，也就是当前的ai正好是fibonacci数列的第j位的时候，我们有两个选择，取当前的ai：
这个操作用转移方程表示就是f(i+1, j+1)
或者不取，就是f(i+1, j)
那么f(i, j)就等于两种取法相加的和，f(i, j) = f(i+1, j+1) + f(i+1, j)

如果当前的值不能取，也就是a[i] != fibonacci[j]，那么只有不取的情况，f(i, j) = f(i+1, j)。为了防止在加法过程中存爆，此处相加后应mod 1000000007。

接下来就是边缘判定：也就是j>=25以及i>=n的情况。由于都已经取完无法再取，那么这种情况下的f(i, j)的值就是1。
需要特别注意的是f(n, 0)应当等于0。按照它的含义，取到第n项(因为数组下标从0开始，所以第n项已经超出了)，当前取的还是第0位，也就是第0位还没取！所以这个不应当成为一个解，f(n, 0)=0!

三、程序框架

先读入，data清-1，data[n][0]取0，然后DP求解f(0, 0)即可。

#include <stdio.h>

const int fibonacci[25] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025};
int a[1000000];
unsigned int data[1000001][26];
int n;

void trydp(int i, int j)
{
    if ((i >= n) || (j >= 25))
    {
        data[i][j] = 1;
        return;
    }
    if (data[i + 1][j] == -1)
        trydp(i + 1, j);
    data[i][j] = data[i + 1][j];
    if (a[i] == fibonacci[j])
    {
        if (data[i + 1][j + 1] == -1)
            trydp(i + 1, j + 1);
        data[i][j] = (data[i][j] + data[i + 1][j + 1]) % 1000000007;
    }
}

int main()
{
    scanf("%d", &n);
    int i, j;
    for (i=0; i<n; ++i)
        scanf("%d", &a[i]);

    long ans = 0;
    for (i=0; i<=n; ++i)
        for (j=0; j<=26; ++j)
            data[i][j] = -1;
    data[n][0] = 0;

    trydp(0, 0);
    printf("%d\n", data[0][0]);

    return 0;
}