自动搬运

查看原文

来自洛谷，原作者为

	0xFF **

搬运于2025-08-24 22:36:05，当前版本为作者最后更新于2022-06-07 20:41:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意

给定一个长度为数列 $a$ 和序列 $b$，同时给定一个数字 $k$。

设一个矩阵 $A$ 满足 $A_{ij} = a_i \times b_j$,求 $A^k$ 的所有元素的和在模 $998244353$ 意义下的答案。

思路分析

我会暴力

我会矩阵快速幂优化！

理论上讲矩阵快速幂是可以通过前两个子任务的，然而由于本人实力有限，经过不断调试还是没能达到预期。

注意到由于 $1 \le n \le 10^5$，甚至无法开一个二维数组存储 $A$ 矩阵。

首先可以发现 $A$ 矩阵是由 $a$ 序列和 $b$ 序列经过操作得到，不妨将 $a$ 序列看作一个 $n$ 行 $1$ 列的矩阵，将 $b$ 序列看作一个 $1$ 行 $n$ 列的矩阵，那么 $a \times b$ 就可以得到 $n$ 行 $n$ 列的矩阵 $A$，这样显然是无法通过本题的。

矩阵乘法虽然没有交换律但是有结合律，所以 $A^k$ 相当于 $(a \times b) ^ k$，将该式展开得到 $(a \times b \times a \times b ......\times b \times a \times b)$，观察除去首项和尾项的 $2k-2$ 项，可以发现他们就是 $(b \times a)^{k-1}$，同时 $b \times a$ 可以得到一个 $1 \times 1$ 的矩阵，也就是一个值即为 $\sum_{i=1}^{n} a_i \times b_i$。这样就可以将矩阵乘法转化成整数的乘法。

接下来我们需要处理刚才忽略的首项和尾项，由于中间 $2k-2$ 项结果是一个值，所以我们可以将此值提出，只对未进行操作的首项和尾项操作。

$a \times b$ 会得到一个 $n$ 行 $n$ 列的矩阵，这个矩阵的元素的和为 $a_1\cdot \sum_{i = 1}^{n} b_i + a_2 \cdot\sum_{i = 1}^{n} b_i +...+a_n \times \sum_{i = 1}^{n} b_i$ 合并同类型可得答案为 $\sum_{i = 1}^{n} a_i \times \sum_{i = 1}^{n} b_i$

综上，我们只需要统计 $a$ 序列的和，$b$ 序列的和以及 $\sum_{i=1}^{n} a_i \times b_i$ 的乘积的和即可得到本题的答案。

const int N = 1e5 + 10;
const int mod = 998244353;

int quickpower(int a,int b){
    int ans=1,base=a;
    while(b){
    	if(b&1){
    		ans*=base;
    		ans%=mod;
		}
		base*=base;
		base%=mod;
		b>>=1;
	}
    return ans;
}

int a[N],b[N];
int ans1 , ans2 ,ans3,ans;
signed main(){
	int n = read() , k = read();
	for(int i=1;i<=n;i++){
		a[i] = read();
		ans1 += a[i];
		ans1 %= mod;
	}
	for(int i=1;i<=n;i++){
		b[i] = read();
		ans2 += b[i];
		ans2 %= mod;
	}
	if(k == 0){
		cout<<n<<endl;
		return 0;
	}
	for(int i=1;i<=n;i++){
		ans3 += a[i] * b[i] % mod;
		ans3 %= mod;
	}
	ans3 = quickpower(ans3,k-1);
	cout<<(ans1 % mod * ans2 % mod * ans3 % mod + mod) % mod<<endl;
	
    return 0;
}