cf_edu_60d

题目大意 : 有魔法石，一个魔法石可以分解为m个普通石，一个魔法师（普通石）占的空间为1，如果一个魔法石一个魔法石往容器里面装，装的时候可以选择分解魔法石为普通石或不分解，询问有多少种方法恰好占满空间为n的容器？分解顺序不同视为方法不同。

设:
dp[i]为放满体积i的方案数
dp[n]=dp[n-1]+dp[n-m],可以用矩阵快速幂加速

#include<bits/stdc++.h>
using namespace std;

//函数参数输入，返回值输出
//特别注意lenth一定要改，不然每次都遍历到最大的矩阵会tle
typedef long long ll;
ll lenth=200;
ll mod=1e9+7;
struct Sarray{
    ll data[200][200];
    //看着改
    Sarray operator *(const Sarray&a){
        Sarray tem;
        for(ll i=0;i<lenth;i++){
            for(ll j=0;j<lenth;j++){
                for(ll k=0;k<lenth;k++){
                    tem.data[i][j]=(tem.data[i][j]+data[i][k]*a.data[k][j])%mod;
                }
            }
        }
        return tem;
    }

    Sarray operator +(const Sarray&a){
        Sarray tem;
        for(ll i=0;i<lenth;i++){
            for(ll j=0;j<lenth;j++){
                tem.data[i][j]=(data[i][j]+a.data[i][j])%mod;
            }
        }
        return tem;
    }

    Sarray(const Sarray&a){
        for(ll i=0;i<lenth;i++){
            for(ll j=0;j<lenth;j++){
                data[i][j]=a.data[i][j];
            }
        }
    }

    Sarray(){
        memset(data,0,sizeof(data));
    }

};

Sarray E;
void ini(){
    for(ll i=0;i<lenth;i++)
        for(ll j=0;j<lenth;j++)
            if(i==j)E.data[i][j]=1;
            else E.data[i][j]=0;
}

Sarray qpow(Sarray a,ll b){
    Sarray tem=E;
    while(b){
        if(b&1)tem=a*tem;
        a=a*a;
        b>>=1;
    }
    return tem;
}

//sigma(p^i) from 0 to n [0,n]
Sarray sigma(Sarray&p,ll n){
    if(n==0)return E;
    if(n==1)return E+p;
    if(n&1) return (E+qpow(p,n/2+1))*sigma(p,n>>1);
    else return (E+qpow(p,n/2+1))*sigma(p,n/2-1)+qpow(p,n>>1);
}
///////////////////////////////////////


int main(){
    ini();

    ll n,m;
    cin>>n>>m;
    lenth=m;
    Sarray p,r;

    p.data[0][0]=1;
    p.data[0][m-1]=1;
    for(ll i=1;i<m;i++){
        p.data[i][i-1]=1;
    }

    r.data[0][0]=2;
    for(ll i=1;i<m;i++){
        r.data[i][0]=1;
    }

    if(n>=m){
        Sarray l=qpow(p,n-m)*r;
        cout<<l.data[0][0]<<endl;
    }
    else{
        cout<<1<<endl;
    }
}