Magic Gems（矩阵快速幂优化dp）

1
2
3
4
5
6
7
8
9
1 0 0……0 0 1                          f[i-1]               f[i]      
1 0 0……0 0 0                          f[i-2]               f[i-1]            
0 1 0……0 0 0                          f[i-3]               f[i-2]               
0 0 1……0 0 0         矩阵   ×         ……             =     ……              
………………                                ……                   ……              
………………                                ……                   ……          
0 0 0……1 0 0                          f[i-m-1]            f[i-m]                 
0 0 0……0 1 0                          f[i-m]              f[i-m+1]                     

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//#pragma GCC optimize(2)
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int inf=8e18;
const int maxn=2e5+100;
const int mod=1e9+7; 
int dp[maxn],n,m;
int b[110][110],a[110][110],tmp[110][110],res[110][110];
void mul(int a[110][110],int b[110][110])
{
	memset(tmp,0,sizeof tmp);
	for(int i=1;i<=m;i++)
	for(int j=1;j<=m;j++)
	for(int k=1;k<=m;k++)
	tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod;
	for(int i=1;i<=m;i++)
	for(int j=1;j<=m;j++)
	a[i][j]=tmp[i][j]%mod;
}
int qpow(int n)
{
	for(int i=1;i<=m;i++)res[i][i]=1;
	while(n)
	{
		if(n&1) mul(res,b);
		mul(b,b);
		n=n>>1;
	}
	int ans=res[1][1]*2%mod;
	for(int i=2;i<=m;i++)ans=(ans+res[1][i])%mod;
	return ans%mod;
}
signed main()
{
	cin>>n>>m;
	b[1][1]=b[1][m]=1;
	for(int i=2;i<=m;i++)b[i][i-1]=1;
	if(n<m)cout<<"1n";
	else if(n==m)cout<<"2n";
	else cout<<qpow(n-m)<<"n";
}