rt，题目如下：

输入两个数 n,k,求 f(n) 的值

其中 f(1)=f(2)=...=f(k)=1，f(n)=f(n-1)+f(n-2)+...+f(n-k)

n<=1e15,k=50

这是我的代码：

#include<bits/stdc++.h>
#define INF 2e18
#define endl '\n'
#define PI acos(-1)
#define pb push_back
#define fi first
#define se second
#define int long long
#define mem(x,v) memset(x,v,sizeof x)
using namespace std;
const int N = 55;
const int MOD = 1e9+7;

int n,k;
struct Matrix{
	int a[N][N];
	void init(){mem(a,0);}
}P,Q;

Matrix operator *(const Matrix &x,const Matrix &y){
	Matrix ans;
	ans.init();
	for(int i=1;i<=k;i++)for(int j=1;j<=k;j++)for(int l=1;l<=k;l++)ans.a[i][j]=(ans.a[i][j]+x.a[i][l]*y.a[l][j]%MOD+MOD)%MOD;
	return ans;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k,P.init(),Q.init();
	if(n<=k)cout<<1,0;
	for(int i=1;i<=k;i++)P.a[1][i]=1;
	Q.a[1][1]=1,Q.a[2][1]=1;
	for(int i=1;i<k;i++)Q.a[i][i+1]=1;
	int t=n-k;
	while(t){
		if(t&1)P=P*Q;
		Q=Q*Q,t>>=1;
	}
	cout<<P.a[1][1]%MOD;
	return 0;
}