P8110

· · 题解

题目大意

给定一个长度为数列 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;
}