题目描述

那N只可爱的奶牛刚刚学习了有关密码的许多算法，终于，她们创造出了属于奶牛的加密方法．由于她们并不是经验十足，她们的加密方法非常简单：第i只奶牛掌握着密码的第i个数字，起始的时候是Ci(0≤Ci<90000000).加密的时候，第i只奶牛会计算其他所有奶牛的数字和，并将这个数字和除以98765431取余．在所有奶牛计算完毕之后，每一只奶牛会用自己算得的数字代替原有的数字．也就是说，

这样，她们就完成了一次加密．    在十一月，奶牛们把这个加密法则告诉了驼鹿卡门，卡门惊呆了．之后，在一个浓雾弥漫的平安夜，卡门与奶牛们：“你们的算法十分原始，很容易就被人破解．所以你们要重复这个加密过程T(1≤T≤1414213562)次，才能达到加密效果．”    这回轮到奶牛们惊呆了．很显然，奶牛们特别讨厌做同样的无聊的事情很多次．经过了漫长的争论，卡门和奶牛们终于找到的解决办法：你被刚来加密这些数字．

输入

第1行输入N和T，之后N行每行一个整数表示初始的Ci．

输出

共N行，每行一个整数，表示T次加密之后的Ci．

样例输入

3 4

1

0

4

样例输出

26

25

29

---

题解

矩阵乘法

令原数和加密后的数构成一个矩阵，设矩阵a为[ci,sum-ci]，则加密一次后的矩阵A为[sum-ci,(n-1)sum-(sum-ci)]，

因为显而易见所有数加密一次后总和变为原来的n-1倍。

推出a乘矩阵[[0,n-1],[1,n-2]]可以得到A，设这个矩阵为b。

按照这个规律，加密T次和T+1次构成的矩阵为a*b^t。

对于每个数，处理出矩阵a，就可以用快速幂解决a*b^t，得到加密t次的数。

注意要开long long

#include 
     
      #include 
      
       #define MOD 98765431typedef long long lint;struct matrix{    int x , y;    lint num[3][3];    matrix operator*(const matrix a) const    {        matrix t;        int i , j , k;        memset(t.num , 0 , sizeof(t.num));        t.x = x , t.y = a.y;        for(i = 1 ; i <= t.x ; i ++ )            for(j = 1 ; j <= t.y ; j ++ )                for(k = 1 ; k <= y ; k ++ )                    t.num[i][j] = (t.num[i][j] + num[i][k] * a.num[k][j]) % MOD;        return t;    }}a , b;lint c[50010];matrix qpow(matrix a , int b){    matrix t;    int i;    t.x = a.x , t.y = a.y;    memset(t.num , 0 , sizeof(t.num));    for(i = 1 ; i <= t.x ; i ++ )        t.num[i][i] = 1;    while(b)    {        if(b & 1)            t = t * a;        a = a * a;        b >>= 1;    }    return t;}int main(){    int n , t , i;    lint sum = 0;    scanf("%d%d" , &n , &t);    for(i = 1 ; i <= n ; i ++ )        scanf("%lld" , &c[i]) , sum = (sum + c[i]) % MOD;    b.x = b.y = 2;    b.num[1][1] = 0 , b.num[1][2] = n - 1 , b.num[2][1] = 1 , b.num[2][2] = n - 2;    b = qpow(b , t);    a.x = 1 , a.y = 2;    for(i = 1 ; i <= n ; i ++ )    {        a.num[1][1] = c[i] , a.num[1][2] = (sum - c[i] + MOD) % MOD;        printf("%lld\n" , (a * b).num[1][1]);    }    return 0;}