P8110 [Cnoi2021] 矩阵题目背景Rumia 喜欢矩阵快速幂而 Cirno 觉得这是平凡的。为了说服 RumiaCirno 提出了这样一个问题。题目描述给定两个长度为n nn的序列{ a n } \{a_n\}{an​}{ b n } \{b_n\}{bn​}与一个整数k kk。设矩阵A AA满足A i j a i × b j A_{ij}a_i\times b_jAij​ai​×bj​求A k A^kAk的所有元素的和在模998244353 998244353998244353意义下的结果。输入格式第一行两个整数n nnk kk。第二行n nn个整数用空格隔开表示{ a n } \{a_n\}{an​}。第三行n nn个整数用空格隔开表示{ b n } \{b_n\}{bn​}。输出格式一行一个整数表示A k A^kAk的所有元素的和在模998244353 998244353998244353意义下的结果。输入输出样例 #1输入 #13 0 1 2 3 4 5 6输出 #13输入输出样例 #2输入 #23 3 1 2 3 4 5 6输出 #292160说明/提示数据范围对于100 % 100\%100%的数据保证1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤1050 ≤ k 998244353 0\le k 9982443530≤k998244353∣ a i ∣ , ∣ b i ∣ ≤ 10 9 |a_i|,|b_i| \le 10^9∣ai​∣,∣bi​∣≤109。子任务Subtask110 pointsn , k ≤ 50 n, k \le 50n,k≤50。Subtask220 pointsn ≤ 100 n \le 100n≤100。Subtask320 pointsn ≤ 1000 n \le 1000n≤1000。Subtask450 points无特殊限制。提示矩阵乘法的定义参考百度百科页面。本题中A 0 A^0A0表示单位矩阵。C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;inlineintread(){intx0,f1;charcgetchar();for(;(c0||c9);cgetchar()){if(c-)f-1;}for(;(c0c9);cgetchar())xx*10(c15);returnx*f;}constintMN1e55;constintmod998244353;intn,a[MN],b[MN],x,pa,pb,k;intksm(intx,inty,intpmod){intres1;x%p;for(intiy;i;i1,xx*x%p)if(i1)resres*x%p;returnres;}signedmain(void){nread(),kread();if(k0){coutnendl;return0;}for(inti1;in;i)a[i]read(),a[i](a[i]modmod)%mod,paa[i],pa%mod;for(inti1;in;i)b[i]read(),b[i](b[i]modmod)%mod,pbb[i],pb%mod;for(inti1;in;i)x(xa[i]*b[i]%mod)%mod;coutpa*pb%mod*ksm(x,k-1)%modendl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容