自动搬运

查看原文

来自洛谷，原作者为

	Leianha 万般皆下品，惟有透彻高

搬运于2025-08-24 22:11:54，当前版本为作者最后更新于2019-09-13 19:23:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

矩阵加速递推

n的范围比较小，k的范围很大，我们可以考虑从n入手。

首先我们知道任何矩阵*单位矩阵都不会改变.所以对于交换操作，我们可以造出一个这样的矩阵：

除了第s、m行，其他每一行都是f[i][i]=1;第s行:f[s][m]=1;第m行:f[m][s]=1;这样我们就完成了交换操作。

对于左移操作，我们也可以造出一个这样的矩阵：

除了第n行，其他每一行都是f[i][i+1]=1;第n行:f[n][1]=1;我们的初始矩阵f[i][1]=a[i];

因为矩阵符合结合律，所以我们可以用类似快速幂的方法加速。然后就可以啦，时间复杂度O($n^3$*log(k)).

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long n,s,m,k;
struct jz
{
	long long c[85][85];
}f,base,lin1,lin2;
jz operator * (const jz &a,const jz &b)//矩阵重载乘号 
{
    jz lin;
    for(int i=1;i<=80;++i)
    {
        for(int j=1;j<=80;++j)
        {
            lin.c[i][j]=0;
            for(int k=1;k<=80;++k)
            {
                lin.c[i][j]+=(a.c[k][j]*b.c[i][k]);
            }
        }
    }
    return lin;
}
jz ksm(jz a,long long b)
{
    jz anss;
    memset(anss.c,0,sizeof(anss.c));
    for(int i=1;i<=n;++i)anss.c[i][i]=1;
    for(;b;b>>=1,a=a*a)
    {
        if(b&1)
        anss=a*anss;
    }
    return anss;
}
void dy(jz x)//调试用的，可以忽略
{
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		cout<<x.c[i][j]<<" ";
		cout<<endl;
	}
}
int main()
{
	cin>>n>>m>>s>>k;
	for(int i=1;i<=n;++i)scanf("%lld",&f.c[i][1]);
	for(int i=1;i<=n;++i)if(i!=s&&i!=m)lin1.c[i][i]=1;
	lin1.c[s][m]=lin1.c[m][s]=1;
	for(int i=1;i<=n-1;++i)lin2.c[i][i+1]=1;
	lin2.c[n][1]=1;
	base=lin1*lin2;
	base=ksm(base,k);
	f=f*base;
	for(int i=1;i<=n;++i)printf("%lld ",f.c[i][1]);
	return 0;
}