自动搬运

查看原文

来自洛谷，原作者为

	Dehydration 临时主页：https://www.luogu.com.cn/paste/22qa5kjy

搬运于2025-08-24 22:18:30，当前版本为作者最后更新于2023-04-12 17:47:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言：

简单的矩阵乘法。

ps：题目。

思路：

令原数和加密后的数构成一个矩阵，设矩阵 $A$ 为 $\begin{bmatrix}c_i&sum-c_i\end{bmatrix}$，则加密一次后的矩阵 $A'$ 为 $\begin{bmatrix}sum-c_i&(n-1)\times sum-(sum-c_i)\end{bmatrix}$，因为显而易见所有数加密一次后总和变为原来的 $n-1$ 倍。

推出 $A$ 乘矩阵 $\begin{bmatrix}0&n-1\\1&n-2\end{bmatrix}$ 可以得到 $A'$，设这个矩阵为 $B$。

按照这个规律，加密 $T$ 次和 $T+1$ 次构成的矩阵为 $A\times B^T$。

对于每个数，处理出矩阵 $A$，就可以用快速幂解决 $A\times B^T$，得到加密 $T$ 次的数。

记住，不开 long long 见祖宗！！！

代码：

#include <bits/stdc++.h>
#define MOD 98765431
typedef long long lint;
struct matrix
{
    int x , y;
    lint num[3][3];
    matrix operator*(const matrix a) const
    {
        matrix t;
        int i , j , k;
        memset(t.num , 0 , sizeof(t.num));
        t.x = x , t.y = a.y;
        for(i = 1 ; i <= t.x ; i ++ )
            for(j = 1 ; j <= t.y ; j ++ )
                for(k = 1 ; k <= y ; k ++ )
                    t.num[i][j] = (t.num[i][j] + num[i][k] * a.num[k][j]) % MOD;
        return t;
    }
}a , b;
lint c[50010];
matrix qpow(matrix a , int b)
{
    matrix t;
    int i;
    t.x = a.x , t.y = a.y;
    memset(t.num , 0 , sizeof(t.num));
    for(i = 1 ; i <= t.x ; i ++ )
        t.num[i][i] = 1;
    while(b)
    {
        if(b & 1)
            t = t * a;
        a = a * a;
        b >>= 1;
    }
    return t;
}
typedef long long LL;
inline LL read()
{
	register LL x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}

int main()
{
    int n , t , i;
    lint sum = 0;
    n=read(),t=read(); 
    for(i = 1 ; i <= n ; i ++ )
        c[i]=read() , sum = (sum + c[i]) % MOD;
    b.x = b.y = 2;
    b.num[1][1] = 0 , b.num[1][2] = n - 1 , b.num[2][1] = 1 , b.num[2][2] = n - 2;
    b = qpow(b , t);
    a.x = 1 , a.y = 2;
    for(i = 1 ; i <= n ; i ++ )
    {
        a.num[1][1] = c[i] , a.num[1][2] = (sum - c[i] + MOD) % MOD;
        printf("%lld\n" , (a * b).num[1][1]);
    }
    return 0;
}//别问我为什么要加快输，因为我要最优解

要看就看我的，我是最优解呢

c++14 + O2 = 最优解。