C11CAL - Tính toán
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#define MAX 55
typedef long long ll;
const ll MOD=1e9+7;
struct matrix {
int m,n;
ll d[MAX][MAX];
matrix(){}
matrix operator * (const matrix &x) {
matrix res (*this);
int a=m;
int b=n;
int c=x.n;
res.m=a;
res.n=c;
int i,j,k;
for (i=0;i<a;i=i+1)
for (j=0;j<c;j=j+1) {
res.d[i][j]=0;
for (k=0;k<b;k=k+1)
res.d[i][j]=(res.d[i][j]+d[i][k]*x.d[k][j])%MOD;
}
return (res);
}
matrix operator ^ (const int &k) {
if (k==1) return (*this);
matrix r=(*this)^(k/2);
r=r*r;
if (k%2==1) r=r*(*this);
return (r);
}
};
matrix fst,mul;
int k,n;
ll c[MAX][MAX];
void finit(void) {
int i,j;
c[0][0]=1;
for (i=1;i<=50;i=i+1) {
c[0][i]=1;
c[i][0]=0;
}
for (i=1;i<=51;i=i+1)
for (j=1;j<=51;j=j+1) {
if (i>j) c[i][j]=0;
if (i==j) c[i][j]=1;
if (i<j) c[i][j]=(c[i-1][j-1]+c[i][j-1])%MOD;
}
}
void construct(void) {
mul.m=k+2;
mul.n=k+2;
int i,j;
for (i=0;i<k+1;i=i+1)
for (j=0;j<k+1;j=j+1)
mul.d[i][j]=c[i][j];
for (i=0;i<k+1;i=i+1) mul.d[k+1][i]=0;
for (i=0;i<k;i=i+1) mul.d[i][k+1]=0;
for (i=0;i<2;i=i+1) mul.d[k+i][k+1]=1;
}
void process(void) {
scanf("%d",&k);
construct();
fst.m=1;
fst.n=k+2;
int i;
for (i=0;i<k+1;i=i+1) fst.d[0][i]=1;
fst.d[0][k+1]=0;
if (n>1) fst=fst*(mul^(n-1));
printf("%lld\n",(fst.d[0][k]+fst.d[0][k+1])%MOD);
}
int main(void) {
finit();
while (scanf("%d",&n)==1) process();
return 0;
}