ACM模版

描述

题解

一看到这道题题目，第一感觉是错别字，因为fei打成fu也不是不可能。然而一细看，发现真的是浮。但是比较直观的发现，这道题和斐波那契有些许关联。

首先，分析数据范围，十分大，一般的递推不可能过，这时可以想到，求十分大的斐波那契数时使用的方法是矩阵快速幂，那么这道题也许也适用，但是这里是浮点型，怎么解决呢？

于是乎，根据Float-Bonacci的定义我们可以发现一个潜在条件，那就是浮点的精度只有一位，那么我们可以通过X10使其转化为：

FB’(n) = FB’(n - 10) + FB’(n - 34)

然后求FB’(10n)即可。

这里出现的难点是单元矩阵的构造原理，我也不明白其中缘由，但是百度到一个矩阵的PPT上讲，在右上角的(n - 1) * (n - 1)的小矩阵中的主对角线上填1，矩阵第n行填对应的系数，其他地方都填0即可。当然，这个矩阵颠倒一下方向什么的也未尝不可。（比如斐波那契的可以构造为0111，也可以构造为1110）

举一个简单的例子：
找到f(n) = 4f(n - 1) - 3f(n - 2) + 2f(n - 4)的第k项。
矩阵构造为：

代码

#include <iostream>
#include <cstdio>
#include <cstring>

#define INF 0x3fffffff

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

ll n;

struct matrix
{
    ll a[35][35];
};

matrix mu(matrix A, matrix B)
{
    matrix t;
    memset(t.a, 0, sizeof(t.a));

    int i, j, k;

    for (i = 1; i <= 34; i++)
    {
        for (j = 1; j <= 34; j++)
        {
            for (k = 1; k <= 34; k++)
            {
                t.a[i][j] += A.a[i][k] * B.a[k][j];
                t.a[i][j] %= mod;
            }
        }
    }
    return t;
}

matrix multi(matrix mat, long long x)
{
    int i;

    matrix b;
    memset(b.a, 0, sizeof(b.a));

    for (i = 1; i <= 34; i++)
    {
        b.a[i][i] = 1;
    }

    while (x)
    {
        if (x & 1)
        {
            b = mu(b, mat);
        }
        x = x >> 1;
        mat = mu(mat, mat);
    }
    return b;
}

void input()
{
    scanf("%lld", &n);
}

void solve()
{
    matrix mat;
    memset(mat.a, 0, sizeof(mat.a));

    int i;
    // 构造单元矩阵
    mat.a[1][10] = mat.a[1][34] = 1;
    for (i = 2; i <= 34; i++)
    {
        mat.a[i][i - 1] = 1;
    }

    // 特判n≤4
    if (n <= 4)
    {
        puts("1");
        return ;
    }
    // n>4
    ll x = (n - 4) * 10;
    matrix res = multi(mat, x);

    ll  ans = 0;
    for (i = 1; i <= 34; i++)
    {
        ans = (ans + res.a[1][i]) % mod;
    }
    printf("%lld", ans);
}

int main()
{
    input();
    solve();

    return 0;
}