题目传送门

• 思路

这道题发现是对一个数列进行操作，

然后又发现操作次数达到了惊人的 k ≤ 1 0 18 k≤10^{18} k≤1018

所以考虑用矩阵乘法。

---

怎么转移呢？（用 n = 3 n=3 n=3 的情况举例）

首先我们知道
形如 B = ( 1 0 0 0 1 0 0 0 1 ) B=\begin{pmatrix}1 & 0&0\\0 &1&0\\0&0&1\end{pmatrix} B=⎝⎛​100​010​001​⎠⎞​ 的矩阵是单位矩阵，且 X × B = X X\times B=X X×B=X。

那么将 a s a_s as​ 和 a m a_m am​ 调位就只需将单位矩阵中的s列和m列调换位置即可。

再考虑如何将n个数都向前平移一位，

和 B B B 类似,第i列的1的行位置就是第i+1列的行位置（n除外）

那么转移矩阵就是 C = ( 0 0 1 1 0 0 0 1 0 ) C=\begin{pmatrix}0 & 0&1\\1 &0&0\\0&1&0\end{pmatrix} C=⎝⎛​010​001​100​⎠⎞​
这样题目中的操作就变成了(原数列为 A A A )

ANS= A × B × C × B × C . . . B × C ⏟ n A\times \underbrace{B \times C\times B\times C...B\times C}_{n} A×n B×C×B×C...B×C​​

然后可以把 S A B = B × C SAB=B\times C SAB=B×C 先算出来，就可以直接计算 S A B n SAB^n SABn 了。

套一个快速幂即可， n = 3 n=3 n=3 可以推广到 n = 80 n=80 n=80 。

• 代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long a[101][101],b[101][101],sab[101][101];
long long ci[2][101],ans[101][101];
int n,s,m,k;
void jzcf()
{
	long long c[101][101];
	for(int i=1; i<=n; i++)
	 for(int j=1; j<=n; j++)
	    c[i][j]=0;
	for(int i=1; i<=n; i++)
	 for(int j=1; j<=n; j++)
	  for(int k=1; k<=n; k++)
	     c[i][j]=c[i][j]+a[i][k]*b[k][j];
	for(int i=1; i<=n; i++)
	 for(int j=1; j<=n; j++)
	    sab[i][j]=c[i][j]; 
}
void jzcf1()
{
	long long c[101][101];
	for(int i=1; i<=n; i++)
	 for(int j=1; j<=n; j++)
	    c[i][j]=0;
	for(int i=1; i<=n; i++)
	 for(int j=1; j<=n; j++)
	  for(int k=1; k<=n; k++)
	     c[i][j]=c[i][j]+sab[i][k]*ans[k][j];
	for(int i=1; i<=n; i++)
	 for(int j=1; j<=n; j++)
	    ans[i][j]=c[i][j];
}
void jzcf2()
{
	long long c[101][101];
	for(int i=1; i<=n; i++)
	 for(int j=1; j<=n; j++)
	    c[i][j]=0;
	for(int i=1; i<=n; i++)
	 for(int j=1; j<=n; j++)
	  for(int k=1; k<=n; k++)
	     c[i][j]=c[i][j]+sab[i][k]*sab[k][j];
	for(int i=1; i<=n; i++)
	 for(int j=1; j<=n; j++)
	    sab[i][j]=c[i][j];
}
void jzcf3()
{
	long long c[101][101];
	for(int i=1; i<=n; i++)
	 for(int j=1; j<=n; j++)
	    c[i][j]=0;
	for(int i=1; i<=1; i++)
	 for(int j=1; j<=n; j++)
	  for(int k=1; k<=n; k++)
	     c[i][j]=c[i][j]+ci[i][k]*ans[k][j];
	for(int i=1; i<=1; i++)
	 for(int j=1; j<=n; j++)
	    ci[i][j]=c[i][j];
}
void ksm(int x)
{
	for(int i=1; i<=n; i++)
	   ans[i][i]=1;
	while(x!=0)
	 {
	 	if(x&1)
	 	  jzcf1();
	 	jzcf2();
	 	x>>=1;
	 }
}
int main()
{
	cin>>n>>s>>m>>k;
	for(int i=1; i<=n; i++)
	   scanf("%lld",&ci[1][i]);
	for(int i=1; i<=n; i++)
	   a[i][i]=1;
    a[s][m]=1,a[m][s]=1,a[s][s]=0,a[m][m]=0;  //交换s和m
    for(int i=1; i<=n-1; i++)
	   b[i+1][i]=1;
	b[1][n]=1;
	jzcf();  //B*C
	ksm(k);
	jzcf3();
	for(int i=1; i<=n; i++)
	   printf("%lld ",ci[1][i]);
	return 0;
}