Educational Codeforces Round 60 D dp + 矩阵快速幂

https://codeforces.com/contest/1117/problem/D

题意

有n个特殊宝石(n<=1e18),每个特殊宝石可以分解成m个普通宝石(m<=100),问组成n颗宝石有多少种方法

题解

• 数据很大：找规律or矩阵快速幂
• 转移方程: dp[i]=dp[i-1]+dp[i-m]
• 因为n<=1e18可以用矩阵快速幂
• 构造矩阵如图:

\[ \left[ \begin{matrix} f[i-1] & f[i-2] & \cdots & f[i-m] \\end{matrix} \right] * \left[ \begin{matrix} 1 & 1 &0 & \cdots & 0 \ 0 & 0 &1 & \cdots & 0 \ \vdots & \vdots &\vdots &\ddots & \vdots \ 0 & 0 &0 &\cdots & 1 \ 1 & 0 &0 &\cdots & 0 \\end{matrix} \right] = \left[ \begin{matrix} f[i] & f[i-1] & \cdots & f[i-m+1] \\end{matrix} \right] \]

代码(矩阵快速幂板子)

#include<bits/stdc++.h>
#define P 1000000007
#define ll long long 
#define M 105
using namespace std;
struct N{
    ll a[M][M];
};
ll m,n,i,j;
N mul(N x,N y){
    N z;
    memset(z.a,0,sizeof(z.a));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++){
                z.a[i][j]+=x.a[i][k]*y.a[k][j]%P;
                z.a[i][j]%=P;
            }
    return z;
}
N pw(N bs,ll x){
    N y;
    memset(y.a,0,sizeof(y.a));
    for(int i=1;i<=n;i++)y.a[i][i]=1;
    while(x){
        if(x&1)y=mul(y,bs);
        bs=mul(bs,bs);
        x>>=1;
    }
    return y;
}
int main(){
    cin>>m>>n;
    N f;memset(f.a,0,sizeof(f.a));  
    f.a[1][1]=1;f.a[n][1]=1;
    for(i=1,j=2;j<=n;j++,i++)f.a[i][j]=1;
    f=pw(f,m);
    cout<<f.a[1][1]%P;
}

Educational Codeforces Round 60 D dp + 矩阵快速幂

原文：https://www.cnblogs.com/VIrtu0s0/p/10502926.html