欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【瞌睡的胡策】训练2.23(数学相关+矩阵快速幂+dp)

程序员文章站 2024-03-23 21:14:58
...

挖坑待填

T3

【瞌睡的胡策】训练2.23(数学相关+矩阵快速幂+dp)
【瞌睡的胡策】训练2.23(数学相关+矩阵快速幂+dp)
事实上这题目的后面还给了错误的公式,我考场上带入公式的内心:MDZZ,ta给的柿子竟然是错的?!

题解:

【瞌睡的胡策】训练2.23(数学相关+矩阵快速幂+dp)
【瞌睡的胡策】训练2.23(数学相关+矩阵快速幂+dp)
直接引图了。

代码:

#include<bits/stdc++.h>

using namespace std;

int n,m;
double x;
struct node{
    double H[65][65];
    node operator *(const node &a) const {
        node ans;
        for (int i=1;i<=(m<<1);i++)
            for (int j=1;j<=(m<<1);j++)
            {
                ans.H[i][j]=0.0;
                for (int k=1;k<=(m<<1);k++)
                    ans.H[i][j]=ans.H[i][j]+H[i][k]*a.H[k][j];
            }
        return ans;
    }
    void clear()
    {
        for (int i=0;i<=(m<<1);i++)
            for (int j=0;j<=(m<<1);j++) H[i][j]=0.0;
    }
    node KSM(int p)
    {
        node a=(*this),ans=(*this);
        p--;
        while (p)
        {
            if (p&1) ans=ans*a;
            a=a*a;
            p>>=1;
        }
        return ans;
    }
};
node H;

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%lf",&m,&n,&x);
        double Sx=sin(x),Cx=cos(x);
        H.clear();

        for (int i=1;i<=m;i++)
        {
            H.H[i][i]=Cx;    
            if (i!=m) H.H[i][i+1]=Sx;
            H.H[i][i+m]=-Sx;
            if (i!=m) H.H[i][i+1+m]=Cx;
            H.H[i+m][i]=Sx;
            H.H[i+m][i+m]=Cx;
        }

        node A=H.KSM(n-1);
        printf("%lf\n",A.H[1][m]*Sx+A.H[m+1][m]*Cx);
    }
    return 0;
}