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;
}