Chino的数列

题目链接：Chino的数列

解题思路

刚刚瞄了一眼题解大佬们的做法，我人都傻了。
反正咱是用矩阵乘法做的……
首先如果要使两个数交换位置，如 $1$ 和 $3$ ，设如下矩阵：
∣ 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 ∣ \begin{vmatrix}0&0&1&0\\0&1&0&0\\1&0&0&0\\0&0&0&1\end{vmatrix} ∣∣∣∣∣∣∣∣​0010​0100​1000​0001​∣∣∣∣∣∣∣∣​
从后往前移一位则是：
∣ 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 ∣ \begin{vmatrix}0&0&0&1\\1&0&0&0\\0&1&0&0\\0&0&1&0\end{vmatrix} ∣∣∣∣∣∣∣∣​0100​0010​0001​1000​∣∣∣∣∣∣∣∣​
做矩阵乘法快速幂即可

code

#include
#include
#include
#define int long long
using namespace std;int n,s,m,k;
int a[100][100];
int h[100][100];
int t[100][100];
int ans[100][100];void csh()
{for(int i=1;i<=n;i++)a[i][i]=1;a[s][s]=0,a[m][s]=1,a[m][m]=0,a[s][m]=1;int tt[100][100];memset(tt,0,sizeof(tt));for(int i=2;i<=n;i++)tt[i][i-1]=1;tt[1][n]=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)t[i][j]+=a[i][k]*tt[k][j];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=t[i][j];
}void add()
{memset(t,0,sizeof(t));for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)t[i][j]+=a[i][k]*ans[k][j];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans[i][j]=t[i][j];
}void cf()
{memset(t,0,sizeof(t));for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)t[i][j]+=a[i][k]*a[k][j];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=t[i][j];
}void end()
{for(int i=1;i<=n;i++)scanf("%lld",&h[1][i]);memset(t,0,sizeof(t));for(int i=1;i<=1;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)t[i][j]+=h[i][k]*ans[k][j];for(int i=1;i<=1;i++)for(int j=1;j<=n;j++)h[i][j]=t[i][j];
}void ksm(int b)
{for(int i=1;i<=n;i++)ans[i][i]=1;while(b){if(b&1)add();cf();b>>=1;}
}signed main()
{cin>>n>>s>>m>>k;csh();ksm(k);end();for(int i=1;i<=n;i++)cout<<h[1][i]<<" ";
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！