gym-103708F Froginald the frog

Froginald the frog

矩阵快速幂

如果没有分隔的话，这就是一个矩阵快速幂求斐波那契的问题

因为有分隔，因此考虑他们分成若干个块，每个块的方案数之积就是答案，显然分隔的长度如果大于 \(1\)，则答案为 \(0\)

有点小卡常，所以如果是比较小的斐波那契询问，直接打表

或者是加个记忆化

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 10;
const ll mod = 1e9 + 7;
ll init[10100];

struct node
{
    ll array[maxn][maxn];
    int x, y;
    node(){x = 0, y = 0;}
    node(int _x, int _y) {x = _x; y = _y;}
    void init(int a)
    {
        for(int i=1; i<=x; i++)
            for(int j=1; j<=y; j++)
                array[i][j] = (i == j) * a;
    }
    node operator *(const node& a) const
    {
        node ans(x, a.y);
        ans.init(0);
        for(int i=1; i<=x; i++)
        {
            for(int j=1; j<=a.y; j++)
            {
                for(int k=1; k<=y; k++)
                {
                    ans.array[i][j] += array[i][k] * a.array[k][j] % mod;
                }
                ans.array[i][j] %= mod;
            }
        }
        return ans;
    }
};

node qpow(node x, int n)
{
    node ans(x.x, x.y);
    ans.init(1);
    while(n)
    {
        if(n & 1) ans = ans * x;
        n >>= 1;
        x = x * x;
    }
    return ans;
}

ll F(ll n)
{
    if(n < 10100) return init[n];
    node x(2, 2);
    x.init(0);
    x.array[1][1] = x.array[1][2] = x.array[2][1] = 1;
    x = qpow(x, n - 2);
    node ans(2, 1);
    ans.array[1][1] = ans.array[2][1] = 1;
    ans = x * ans;
    return ans.array[1][1];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    init[2] = init[1] = 1;
    for(int i=3; i<10100; i++)
        init[i] = (init[i - 1] + init[i - 2]) % mod;
    vector<int>num(m + 1);
    for(int i=1; i<=m; i++) cin >> num[i];
    num[0] = n + 1;
    sort(num.begin(), num.end());
    ll ans = 1, pre = 0;
    for(int i=0; i<num.size(); i++)
    {
        if(num[i] == pre) {ans = 0; break;}
        ans = ans * F(num[i] - pre) % mod;
        pre = num[i] + 1;
    }
    cout << ans << endl;
    return 0;
}