C11CAL-MathMul.cpp

/*
 * C11CAL.Mat.CPP
 *
 *  Created on: Nov 26, 2011
 *      Author: vanhoa
 */

#include<stdlib.h>
#include<stdio.h>
#include<string.h>

typedef long long TLL;
typedef TLL Mat[52][52];

inline TLL nm(TLL x){return ((x%1000000007)+1000000007)%1000000007;}

inline void MatMul(int n, Mat& a, Mat& b){
	Mat ret;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++){
			ret[i][j]=0;
			for(int k=0;k<n;k++){
				ret[i][j]+=nm(a[i][k]*b[k][j]);
			}
			ret[i][j]=nm(ret[i][j]);
		}
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			a[i][j]=ret[i][j];
}

void printMat(Mat a, int n){
	printf("****\n");
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			printf("%4lld",a[i][j]);
		}
		printf("\n");
	}
}
#define printMat(a,b)

Mat M, MR;
TLL F(long long n, int k){
	//Vecto trang thai:
	// v=Trans([i^0,i^1,...,i^k,S(k,i)])
	// |v|=k+2
	//Chuyen trang thai: v'= M * v
	//[ 1 ]   [1, 0, ..., 0, 0]   [ 1 ]
	//[i^1]   [1, 1, ..., 0, 0]   [j^1]
	//[...] = [...............] * [...]
	//[i^k]   [1, k, ..., 1, 0]   [j^k]
	//[ S']   [1, k, ..., 1, 1]   [ S ]
	// v[0]=[1,0,0,0,..,0]
	// ** Khoi tao ma tran M
		memset(M,0,sizeof(M));
		for(int i=0;i<=k;i++){
			M[i][0]=1;
			for(int j=1;j<=i;j++){
				M[i][j]=nm(M[i-1][j-1]+M[i-1][j]);
			}
		}
		for(int i=0;i<=k;i++) M[k+1][i]=M[k][i];
		M[k+1][k+1]=1;
	// ** Khoi tao MR = ma tran don vi
		for(int i=k+1;i>=0;i--)
			for(int j=k+1;j>=0;j--)
				MR[i][j]=i==j;
	// ** Tinh MR
		printMat(M,k+2);
		printMat(MR,k+2);
		for(TLL i=1;i<=n;i<<=1){
			if(n&i){
				MatMul(k+2, MR, M);
				printMat(MR,k+2);
			}
			printMat(M,k+2);
			MatMul(k+2, M, M);
		}
		printMat(MR,k+2);
	return MR[k+1][0];
}

int main(){
	long long n; int k;
	while(scanf("%lld%d",&n,&k)==2) printf("%lld\n",F(n,k));
}