139 lines
3.3 KiB
C++
139 lines
3.3 KiB
C++
#include <stdio.h>
|
|
#include <string.h>
|
|
#include <iostream>
|
|
#define MAX_DIMENSION 35
|
|
using namespace std;
|
|
typedef __int64 MATRIX_TYPE;
|
|
typedef __int64 MAX_INT_TYPE;
|
|
typedef MATRIX_TYPE Matrix[MAX_DIMENSION][MAX_DIMENSION];
|
|
int ndim=MAX_DIMENSION;
|
|
int mod=1234567891;
|
|
void m_zero(Matrix x)
|
|
{
|
|
memset(x, 0, sizeof(MATRIX_TYPE)*MAX_DIMENSION*MAX_DIMENSION);
|
|
}
|
|
void m_one(Matrix x)
|
|
{
|
|
int i;
|
|
m_zero(x);
|
|
for(i=0;i<ndim;++i)x[i][i]=1;
|
|
}
|
|
void m_copy(Matrix src,Matrix dest)
|
|
{
|
|
memcpy(dest,src, sizeof(MATRIX_TYPE)*MAX_DIMENSION*MAX_DIMENSION);
|
|
}
|
|
void m_add(Matrix x,Matrix y,Matrix z)
|
|
{
|
|
int i,j;
|
|
for(i=0;i<ndim;i++)
|
|
for(j=0;j<ndim;j++)
|
|
if(mod<=1)z[i][j]=x[i][j]+y[i][j];
|
|
else z[i][j]=(x[i][j]+(MAX_INT_TYPE)y[i][j])%mod;//module
|
|
}
|
|
void m_multiple(Matrix a,Matrix b,Matrix c)
|
|
{
|
|
int i,j,k;
|
|
MAX_INT_ t;
|
|
for(i=0;i<ndim;i++)
|
|
for(j=0;j<ndim;j++)
|
|
{
|
|
t=0;
|
|
if(mod<=1)
|
|
for(k=0;k<ndim;k++) t+=a[i][k]*b[k][j];
|
|
else
|
|
for(k=0;k<ndim;k++){
|
|
t+=(a[i][k]*(MAX_INT_TYPE)b[k][j])%mod;
|
|
t%=mod;
|
|
}
|
|
c[i][j]=t;
|
|
}
|
|
}
|
|
void m_pow_with_saved(Matrix x_p[],unsigned int n, Matrix y)
|
|
{
|
|
Matrix temp;
|
|
m_one(y);
|
|
for(int k=1;n;++k,n>>=1)
|
|
{
|
|
if ((n & 1) != 0)
|
|
{
|
|
m_multiple(x_p[k],y,temp);
|
|
m_copy(temp,y);
|
|
}
|
|
}
|
|
}
|
|
void m_pow_sum1(Matrix x_p[],unsigned int n, Matrix y)
|
|
{
|
|
m_zero(y);
|
|
if(n==0)return;
|
|
if(n==1) m_copy(x_p[1],y);
|
|
else
|
|
{
|
|
Matrix temp;
|
|
m_pow_sum1(x_p,n>>1,temp);
|
|
m_add(temp,y,y);
|
|
Matrix temp2;
|
|
m_pow_with_saved(x_p,n>>1,temp2);
|
|
Matrix temp3;
|
|
m_multiple(temp,temp2,temp3);
|
|
m_add(temp3,y,y);
|
|
if(n&1)
|
|
{
|
|
m_multiple(temp2,temp2,temp3);
|
|
m_multiple(temp3,x_p[1],temp2);
|
|
m_add(temp2,y,y);
|
|
}
|
|
}
|
|
}
|
|
void m_pow_sum(Matrix x, unsigned int n, Matrix y)
|
|
{
|
|
unsigned int i=0,logn,n2=n;
|
|
for(logn=0,n2=n;n2;logn++,n2 >>= 1);
|
|
Matrix *pow_arry=new Matrix[logn==0?2:(logn+1)];
|
|
m_one(pow_arry[0]);
|
|
m_copy(x,pow_arry[1]);
|
|
for(i=1;i<logn;i++)
|
|
{
|
|
m_multiple(pow_arry[i],pow_arry[i],pow_arry[i+1]);
|
|
}
|
|
m_pow_sum1(pow_arry,n,y);
|
|
delete []pow_arry;
|
|
}
|
|
void view_mat(Matrix a, int n)
|
|
{
|
|
for(int i = 0; i < n; i++)
|
|
{
|
|
for(int j = 0; j < n; j++)
|
|
cout << a[i][j] << " ";
|
|
cout << endl;
|
|
}
|
|
}
|
|
int main(void)
|
|
{
|
|
int cas;
|
|
scanf("%d", &cas);
|
|
while(cas--)
|
|
{
|
|
int n, k;
|
|
scanf("%d %d", &n, &k);
|
|
Matrix a;
|
|
ndim = k + 1;
|
|
m_zero(a);
|
|
for(int i = 0; i <= k; i++)
|
|
{
|
|
if(i == 0)
|
|
continue;
|
|
a[i][i] = i;
|
|
a[i - 1][i] = k - i + 1;
|
|
}
|
|
Matrix asum, res, addsum, f1, ans;
|
|
m_one(res);
|
|
m_pow_sum(a, n - 1, asum);
|
|
m_add(res, asum, addsum);
|
|
m_zero(f1);
|
|
f1[0][1] = k;
|
|
m_multiple(f1, addsum, ans);
|
|
printf("%d\n", ((ans[0][k] % mod) + (__int64)mod) % mod);
|
|
}
|
|
return 0;
|
|
}
|