Skip to content

Instantly share code, notes, and snippets.

@vhqtvn vhqtvn/C11CAL-MathMul.cpp Secret
Created Nov 7, 2015

Embed
What would you like to do?
/*
* 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));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.