本文同步更新于洛谷博客

题目描述

给定两个长度为 \(n\) 的序列 \(\{a_n\},\{b_n\}\) 与一个整数 \(k\)。
设矩阵 \(A\) 满足 \(A_{ij}=a_i\times b_j\)，求 \(A^k\) 的所有元素的和在模 \(998244353\) 意义下的结果。

题解

（\(k=0\) 的时直接输出 \(n\)，下面只讨论 \(k>0\) 的情况）
比赛的时候打了个暴力把 \(A^2\) 和 \(A^3\) 都求出来了，观察发现答案为 \(\sum a_i\times\sum b_i\times(\sum a_ib_i)^{k-1}\)，现在用数学归纳法来证明一下。
设 \(A^{k-1}\) 为矩阵 \(B\)，\(A^k\) 为矩阵 \(C\)。
当 \(m=1\) 时，由矩阵乘法的定义可算出矩阵 \(A\)，不难发现和为 \(\sum a_i\times\sum b_i\)。
不妨假设 \(m=k-1\) 时，\(\sum\sum B_{ij}=\sum a_i\times\sum b_i\times(\sum a_ib_i)^{k-2}\)，
则 \(m=k\) 时，如下图可得 \(C_{ij}=\sum\sum B_{ij}a_ib_j\)，则 \(\sum\sum C_{ij}=\sum\sum B_{ij}\times\sum a_ib_i=\sum a_i\times\sum b_i\times(\sum a_ib_i)^{k-1}\)，证毕。

\(\begin{bmatrix} a_1b_1&a_1b_2&...&a_1b_n \\ a_2b_1&a_2b_2&...&a_2b_n \\ ...&...&...&... \\ a_nb_1&a_nb_2&...&a_nb_n \end{bmatrix} \begin{bmatrix} B_{11}&B_{12}&...&B_{1n}\\ B_{21}&B_{22}&...&B_{2n}\\ ...&...&...&...\\ B_{n1}&B_{n2}&...&B_{nn} \end{bmatrix}\)

最后用快速幂求解即可。

注意

\(\{a_n\}\) 和 \(\{b_n\}\) 中可能会有负数，注意取模。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll p=998244353;
const int maxn=1e5+5;
int n;
ll k,a[maxn],b[maxn],x,y,s;
ll quickpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
	if(b&1)
	    res=res*a%p;
	b>>=1;
	a=a*a%p;
    }
    return res;
}
int main()
{
    scanf("%d%lld",&n,&k);
    if(!k)
    {
	printf("%d\n",n);
	return 0;
    }
    for(int i=1;i<=n;i++)
    {
	scanf("%lld",&a[i]);
	x=(x+a[i])%p;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&b[i]);
	y=(y+b[i])%p;
    }
    for(int i=1;i<=n;i++)
	s=(s+a[i]*b[i]%p)%p;
    printf("%lld\n",(x*y%p*quickpow(s,k-1)%p+p)%p);
    return 0;
}