#include #include #include typedef struct double_matrix{ int r,c; double **data; }doubleMatrix; void* newDoubleMatrix(doubleMatrix *a,int r,int c,void *WorkMemory){ int i; a->r=r; a->c=c; a->data = (double**)WorkMemory; WorkMemory = (void*)(a->data + r); for(i=0;idata[i] = (double*)WorkMemory; WorkMemory = (void*) (a->data[i] + c); } return WorkMemory; } void doubleMatrixSetZero(doubleMatrix *a){ int i,j; for(i=0; i<(a->r); i++) for(j=0; j<(a->c); j++) a->data[i][j]=0; } void doubleMatrixSetIdentity(doubleMatrix *a){ int i,mx; mx=a->r; if(mx>a->c) mx=a->c; doubleMatrixSetZero(a); for(i=0;idata[i][i] = 1; } void doubleMatrixMultiple(doubleMatrix *a,doubleMatrix *b,doubleMatrix *res){ int i,j,k; doubleMatrixSetZero(res); for(i=0;i<(res->r);i++){ for(k=0;k<(b->r);k++) if(a->data[i][k]!=0.0){ for(j=0;j<(res->c);j++) res->data[i][j] += a->data[i][k] * b->data[k][j]; } } } void doubleMatrixPower(doubleMatrix *a,doubleMatrix *res,int k,void *WorkMemory){ int i,j,n=a->r; doubleMatrix tmp1,tmp2; res->r=res->c=n; if(k==0){ doubleMatrixSetIdentity(res); return; } if(k==1){ for(i=0;idata[i][j]=a->data[i][j]; return; } if(k==2){ doubleMatrixMultiple(a,a,res); return; } WorkMemory = newDoubleMatrix(&tmp1,n,n,WorkMemory); doubleMatrixPower(a, &tmp1, k/2, WorkMemory); if(k%2==0) doubleMatrixMultiple(&tmp1,&tmp1,res); else { WorkMemory = newDoubleMatrix(&tmp2,n,n,WorkMemory); doubleMatrixMultiple(&tmp1,&tmp1,&tmp2); doubleMatrixMultiple(a,&tmp2,res); } } int main(){ int T; void *mem = malloc(10000000); scanf("%d",&T); while(T--){ int M, N; double X, cosX, sinX; int i; doubleMatrix mt, pw; double res; void *mem_next; scanf("%d%d%lf",&M,&N,&X); cosX = cos(X); sinX = sin(X); mem_next = newDoubleMatrix(&mt,2*M,2*M,mem); /* create a matrix */ mem_next = newDoubleMatrix(&pw,2*M,2*M,mem_next); N--; doubleMatrixSetZero(&mt); for(i=0;i