P8110 [Cnoi2021] 矩阵 题解

P8110 [Cnoi2021] 矩阵 题解

题目链接

我的博客

思路

考虑一个矩阵乘法 \(B=A \times A\)。那么 \(B\) 就是 \(A^2\)。

把它展开。

\[B_{i,j}=\sum_{k=1}^{n} A_{i,k} \times A_{k,j} =\sum_{k=1}^n a_ib_ka_kb_j =a_ib_j \times \sum_{k=1}^n a_kb_k=A_{i,j} \times \sum_{x=1}^n a_xb_x \]

所以就转化成给每一项都乘上 \(\sum_{x=1}^n a_xb_x\)，这部分可以用快速幂完成。

再来看 \(A_{i,j}\)。

\[\sum_{i=1}^n \sum_{j=1}^n A_{i,j}=\sum_{i=1}^n \sum_{j=1}^n a_ib_j=\left( \sum_{i=1}^n a_i \right) \times \left( \sum_{j=1}^n b_j \right) \]

因此答案就是

\[\left( \sum_{i=1}^n a_i \right) \times \left( \sum_{j=1}^n b_j \right) \times \left( \sum_{x=1}^n a_xb_x \right)^{k-1} \]

时间复杂度 \(O\left(n+ \log k\right)\)

代码

const int N=1e5+10;
const ll mod=998244353;
int n,k;
ll a[N],b[N];
ll suma,sumb,sumc,ans;//不要忘记开long long
ll ksm(ll a,int b){//快速幂ll res=1ll;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res%mod;
}
signed main(){n=Read();k=Read();for(int i=1;i<=n;i++) {a[i]=(Read()+mod+mod)%mod;//注意 a 的范围，可能是负数，所以要先都变正suma+=a[i];suma%=mod;}for(int j=1;j<=n;j++) {b[j]=(Read()+mod+mod)%mod;sumb+=b[j];sumb%=mod;}for(int i=1;i<=n;i++){sumc+=a[i]*b[i]%mod;//同上sumc%=mod;}if(k==0){//一定要特判printf("%d\n",n);return 0;}sumc=ksm(sumc,k-1)%mod;ans=suma*sumb%mod*sumc%mod;//别忘了取模printf("%lld\n",ans);return 0; 
}