Magic Gems 矩阵乘法

itdef / 2024-09-02 / 原文

// Magic Gems.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
http://oj.daimayuan.top/course/22/problem/1046

题目描述
Reziba 拥有无限多个魔法宝石，每个魔法宝石的大小为 1
 单元。每个魔法宝石可以被分解为 m
 个普通宝石，每个普通宝石的大小也是 1
 单元。

现在 Reziba 需要选出一部分魔法宝石，并且选择其中一些进行分解，使得最后的宝石能够占满 n
 单元大小的空间。请问有多少种不同的选择与分解方案，请输出答案模 109+7
 。（如果两种方案选择的魔法宝石的数量不同，或者分解的魔法宝石在序列中的位置不同就认为是不同的方案）。

输入格式
第一行两个整数 n,m
。

输出格式
一行一个数表示答案模 109+7
 的结果。

样例输入
4 2
样例输出
5
数据范围
对于 100%
 的数据，保证 1≤n≤10^18,2≤m≤100
。
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>


using namespace std;

const int N = 100;
const int P = 1000000007;;

int n;
long long k;
long long f[N + 1], a[N + 1][N + 1];

inline void aa() {
    long long  w[N + 1][N + 1];
    memset(w, 0, sizeof w);
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= n; k++) {
            if(a[i][k])
                for (int j = 1; j <= n; j++) {
                    if (a[k][j])
                        w[i][j] += a[i][k] * a[k][j], w[i][j] %= P;
                }
        }
    }

    memcpy(a, w, sizeof a);
}


inline void fa() {
    long long w[N + 1];
    memset(w, 0, sizeof w);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            w[i] += f[j] * a[j][i], w[i] %= P;
    memcpy(f, w, sizeof f);
}

inline void matrixpow(long long k) {
    for (; k; k >>= 1) {
        if (k & 1) {
            fa();
        }
        aa();
    }
}

int main()
{
    scanf("%lld%d",&k,&n);
    for (int i = 2; i <= n; i++)
        a[i][i - 1] = 1;
    a[1][n] = 1;
    a[n][n] = 1;
    f[n] = 1;
    matrixpow(k);
    printf("%lld\n",f[n]);
}