【LOJ NOI Round#2 Day1 T1】单枪匹马（矩阵乘法）

题目传送门

操作二要求的东西是一个循环迭代的东西，手推相邻两项找下规律，发现相邻两项的分子分母间含有线性关系，考虑用矩阵乘法求解。对于 ([1,n])的询问，从后往前倒推， (x_{n-1}=a_{n-1} imes x_{n} + y_{n})， (y_{n-1}=x_{n})，其中 (x_{n}=a_{n},y_{n}=1)， (x_{i},y_{i})分别代表从后往前计算到第 (i)项时的分子分母，第 (i)个数的初始矩阵为 (left[ egin{matrix} 0 & 1 \ 1 & a_{i} end{matrix} ight])，这样从后往前乘，最终得到的矩阵的 (matrix[1][2])即为 (y)值， (matrix[2][2])即为 (x)值。所以做一下前缀积即可，用数组 (pre)表示。对于 ([l,r])的询问，计算逆矩阵前缀积，用数组 (inv\_pre)表示，第 (i)项的初始逆矩阵为 (left[ egin{matrix} -a_{i} & 1 \ 1 & 0 end{matrix} ight])。答案等于 (inv\_pre[l-1] imes pre[r])，因为矩阵乘法不满足交换律，所以注意乘的顺序，(inv\_pre)要倒着乘，具体看代码。

#include<cstdio>
#include<cstring>
const int mod = 998244353;
const int N = 1e6 + 5;

struct Matrix{
    int a[3][3];
    Matrix() { memset(a, 0, sizeof(a));	}
    Matrix operator *(const Matrix &ret)const{
        Matrix ans;
        for(int k = 1; k <= 2; ++k)
        	for(int i = 1; i <= 2; ++i)
        		for(int t = 1; t <= 2; ++t)
        			ans.a[i][t] = (ans.a[i][t] + 1LL * a[i][k] * ret.a[k][t]) % mod;
        return ans;
    }    
}pre[N], inv_pre[N];

int n, m, type, cnt;

void add(int pos, int num){
    pre[pos].a[1][2] = pre[pos].a[2][1] = 1;
    pre[pos].a[2][2] = num;
    inv_pre[pos].a[1][2] = inv_pre[pos].a[2][1] = 1;
    inv_pre[pos].a[1][1] = mod - num;
    pre[pos] = pre[pos - 1] * pre[pos];
    inv_pre[pos] = inv_pre[pos] * inv_pre[pos - 1];  // 倒着乘
}

int main(){
    scanf("%d%d%d", &n, &m, &type);  cnt = n;
    pre[0].a[1][1] = pre[0].a[2][2] = 1;
    inv_pre[0].a[1][1] = inv_pre[0].a[2][2] = 1;
    for(int i = 1, x; i <= n; ++i){
        scanf("%d", &x);
        add(i, x);
    }
    int opt, l, r, x, last = 0;
    while(m--){
        scanf("%d", &opt);
        if(opt == 1){
            scanf("%d", &x);
            if(type)  x ^= last;
            add(++cnt, x);
        }
        else{
            scanf("%d%d", &l, &r);
            if(type)  l ^= last, r ^= last;
            Matrix p = inv_pre[l - 1] * pre[r];
            int x = p.a[2][2],  y = p.a[1][2];
            last = x ^ y;
            printf("%d %d
", x, y);
        }
    }
    return 0;
}