讨论 / 想知道奇葩答案吗?
a651291702 2015-10-08 20:28:11
点我顶贴 收藏 删除
其实这是一道快速幂+矩阵的题目

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;

}

帅哥的程序在此

查看更多回复
提交回复