10.2 D. Magic Gems
题目大意（自己总结
给你n个空间，可以放魔法石头，也可以放普通石头，可以将一个魔法石变成M个普通石头，需要M个空间可以有多少种不同的宝石组合，从而使所占用的空间总数为 N 个单位？打印答案，模数为 1000000007 ( 109+7 )。如果雷兹巴所需的魔法宝石数量不同，或者雷兹巴需要分割的宝石的指数不同，那么这两种配置就会被认为是不同的。
输入包含一行由 2 和 M 组成的整数 N 和 M ( 1≤N≤1018 ， 2≤M≤100 )。
题目主要实现思路
首先考虑第一个空间，可以考虑到转移方程dp【i] =dp [ i -1 ]，
如果i>=m，可以加上将这m个空间成普通宝石得数量也就是dp[ i ] +=dp[i - m] ;由于n够大，用矩阵快速幂加速递推
#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 1e6 + 10;const int mod = 1e9 + 7;using martrix = vector<vector<int>>;martrix mul(martrix &a, martrix &b){ int n = a.size(); int m = b[0].size(); martrix c = martrix(n, vector<int>(m, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < a[i].size(); j++) { for (int k = 0; k < m; k++) { c[i][k] = (a[i][j] * b[j][k] + c[i][k]) % mod; } } } return c;}martrix m_pow(martrix a, int b, martrix &f0){ martrix res = f0; while (b) { if (b & 1) { res = mul(a, res); } b >>= 1; a = mul(a, a); } return res;}void solve(){ int n, m; cin >> n >> m; vector<vector<int>> f0(m, vector<int>(1, 0)); f0[m - 1][0] = 1; martrix A(m, vector<int>(m, 0)); for (int i = 0; i < m - 1; i++) { A[i][i + 1] = 1; } A[m - 1][0] = 1; A[m - 1][m - 1] = 1; auto res = m_pow(A, n, f0); cout << res[m - 1][0] << '\n';}signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T; T = 1; // cin >> T; while (T--) solve(); return 0;}