C++11(clang++ 3.9) 解法, 执行用时: 64ms, 内存消耗: 704K, 提交时间: 2019-07-26 19:52:34

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long

const double eps=1e-12;
const ll inf=1e9;
const ll mod=1e9+7;
const int maxn=1e5+10;
const int maxm=60+10;

int mm;
double v[maxm];

struct mat
{
    double a[maxm][maxm];
    mat()
    {
        memset(a,0,sizeof(a));  ///must ; for mat z(variable not in constant)
    }
    void init()
    {
        int i;
        memset(a,0,sizeof(a));
        for (i=1;i<=mm;i++)
            a[i][i]=1;
    }
    mat operator*(const mat &y) const
    {
        mat z;
        int i,j,k;
        for (k=1;k<=mm;k++)
            for (i=1;i<=mm;i++)
                for (j=1;j<=mm;j++)
                    z.a[i][j]+=a[i][k]*y.a[k][j];
        return z;
    }
}mat0,mat1;

mat mul(mat a,int b)
{
    mat y;
    y.init();
    while (b)
    {
        if (b&1)
            y=y*a;
        a=a*a;
        b>>=1;
    }
    return y;
}


int main()
{
    int t,m,M,n,i,j;
    double x,tot;
    mat mat0,mat1;
    scanf("%d",&t);
    m=30,mm=60;
    while (t--)
    {
        scanf("%d%d%lf",&M,&n,&x);
//        mm=m<<1;
        ///写成30,60:避免覆盖 当n=1,2时 (v[1],v[2],v[m+1])
        ///i=1..m F[N-1][i] ; j=(i=1..n)+m F[N-2][i]
        ///F[N]
        memset(mat0.a,0,sizeof(mat0.a));
        for (i=1;i<=m;i++)
        {
            mat0.a[i][i]=cos(x)*2;
            mat0.a[i][i+m]=-1;
            ///注意 mat0.a[p][q] * v[q] [...][p]使用[...][q]
            if (i!=1)
                mat0.a[i][i-1]=sin(x);
        }
        ///F[N-1]
        for (i=m+1;i<=mm;i++)
            mat0.a[i][i-m]=1;
        ///F[2]
        memset(v,0,sizeof(v));
        v[1]=sin(x*2);
        v[2]=sin(x)*sin(x);
        ///F[1]
        v[m+1]=sin(x);
//        v[1]=sin(x);
//        for (i=1;i<=m;i++)
//            v[i]=i;
//        ///F[0]
//        for (i=m+1;i<=mm;i++)
//            v[i]=0;

        ///F[n+1] F[n]
        mat1=mul(mat0,n-1);
//        mat1=mul(mat0,n);
        tot=0;
        ///F[n] right part
        for (j=1;j<=mm;j++)
            tot+=mat1.a[m+M][j]*v[j];

        ///另外的写法：初始的矩阵y(in mul function)=v，快速幂直接在main函数内写

        if (!(fabs(tot)>eps && tot<0))
            printf("+");
        else
        {
            printf("-");
            tot=-tot;
        }
        while (tot<1)
            tot*=10;
        while (tot>=10)
            tot/=10;
        printf("%d\n",(int)tot);
    }
    return 0;
}
/*
4
1 1 1
2 2 1
3 3 1
4 4 1
sin(1)=0.84147
‭0.8414709848078965066525023216303‬
‭0.70807341827357119349878411475038‬
‭0.595821144644523‬
‭0.50136796566561970416888809186316‬

2
1 0 1
2 0 1
*/