Educational Codeforces Round 60 (Rated for Div. 2) - D. Magic Gems（动态规划+矩阵快速幂）

Problem   Educational Codeforces Round 60 (Rated for Div. 2) - D. Magic Gems

Time Limit: 3000 mSec

Problem Description

Input

The input contains a single line consisting of 2 integers N and M (1≤N≤10^18, 2≤M≤100).

Output

Print one integer, the total number of configurations of the resulting set of gems, given that the total amount of space taken is N units. Print the answer modulo 1000000007.

Sample Input

4 2

Sample Output

5

题解：很简单的dp，考虑第一个数分裂不分裂，dp[n] = dp[n - m] + dp[n - 1]，其中dp[n]就是站n个单位空间的方法数，由于N比较大，所以很明显要用矩阵快速幂，写这篇题解同时提醒自己快速幂之前一定要判断指数是否非负。

 #include <bits/stdc++.h>

 using namespace std;

 #define REP(i, n) for (int i = 1; i <= (n); i++)

 #define sqr(x) ((x) * (x))

 const int maxn =  + ;

 const int maxm =  + ;

 const int maxs =  + ;

 typedef long long LL;

 typedef pair<int, int> pii;

 typedef pair<double, double> pdd;

 const LL unit = 1LL;

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const double inf = 1e15;

 const double pi = acos(-1.0);

 const int SIZE =  + ;

 const LL MOD = ;

 struct Matrix

 {

     int r, c;

     LL mat[SIZE][SIZE];

     Matrix() {}

     Matrix(int _r, int _c)

     {

         r = _r;

         c = _c;

         memset(mat, , sizeof(mat));

     }

 };

 Matrix operator*(Matrix a, Matrix b)

 {

     Matrix s(a.r, b.c);

     for (int i = ; i < a.r; i++)

     {

         for (int k = ; k < a.c; k++)

         { //j, k交换顺序运行更快

             for (int j = ; j < b.c; j++)

             {

                 s.mat[i][j] = (s.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;

             }

         }

     }

     return s;

 }

 Matrix pow_mod(Matrix a, LL n)

 {

     Matrix ret(a.r, a.c);

     for (int i = ; i < a.r; i++)

     {

         ret.mat[i][i] = ; //单位矩阵

     }

     Matrix tmp(a);

     while (n)

     {

         if (n & )

             ret = ret * tmp;

         tmp = tmp * tmp;

         n >>= ;

     }

     return ret;

 }

 LL n, m;

 int main()

 {

     ios::sync_with_stdio(false);

     cin.tie();

     //freopen("input.txt", "r", stdin);

     //freopen("output.txt", "w", stdout);

     cin >> n >> m;

     if (n < m)

     {

         cout <<  << endl;

         return ;

     }

     Matrix ori = Matrix(m, );

     for (int i = ; i < m; i++)

     {

         ori.mat[i][] = unit;

     }

     Matrix A = Matrix(m, m);

     A.mat[][] = unit;

     A.mat[][m - ] = unit;

     for (int i = ; i < m; i++)

     {

         A.mat[i][i - ] = unit;

     }

     Matrix ans = pow_mod(A, n - m + );

     ori = ans * ori;

     cout << ori.mat[][] << endl;

     return ;

 }

Educational Codeforces Round 60 (Rated for Div. 2) - D. Magic Gems（动态规划+矩阵快速幂）的相关教程结束。