m=1 ans=2
m=2 2 4 6 10 16 26
m=3 2 4 6 8 14 26 48
可以写成矩阵 然后加上快速幂便可以
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long a[8][8],b[8][8],c[8][8];
int kk[8];
const int Mod=33554432;
long long n;
int m;
void chen(long long h1[][8],long long h2[][8])
{
memset(c,0,sizeof(c));
int i,j,k;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
for(k=1;k<=m;k++)
c[i][j]=(c[i][j]+(h1[i][k]*h2[k][j])%Mod)%Mod;
memcpy(a,c,sizeof(a));
}
void solve(long long k)
{
if(k<=1) return;
solve(k/2);
chen(a,a);
if(k%2==1) chen(a,b);
}
void mem()
{
int i;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for(i=1;i<=m-1;i++)
{
a[i][i+1]=1;
b[i][i+1]=1;
}
for(i=1;i<=m;i++)
{
a[m][i]=1;
b[m][i]=1;
}
return;
}
int main()
{
int i,j;
scanf("%lld%d",&n,&m);
kk[0]=1;
for(i=1;i<=m;i++) kk[i]=kk[i-1]*2;
mem();
if(n==1 || m==1) {printf("2\n");return 0;}
solve(n-1);
long long ans=0;
for(i=1;i<=m;i++)
ans=(ans+(kk[i]*a[1][i])%Mod)%Mod;
printf("%lld",ans);
return 0;
}
帅哥的程序在此