Description
那N只可爱的奶牛刚刚学习了有关密码的许多算法，终于，她们创造出了属于奶牛的加密方法．由于她们并不是经验十足，她们的加密方法非常简单：
第i只奶牛掌握着密码的第i个数字，起始的时候是Ci(0≤Ci<90000000).加密的时候，
第i只奶牛会计算其他所有奶牛的数字和，并将这个数字和除以98765431取余．在所有奶牛计算完毕之后，每一只奶牛会用自己算得的数字代替原有的数字．也就是说，
这样，她们就完成了一次加密． 在十一月，奶牛们把这个加密法则告诉了驼鹿卡门，卡门惊呆了．之后，在一个浓雾弥漫的平安夜，卡门与奶牛们：“你们的算法十分原始，很容易就被人破解．所以你们要重复这个加密过程T(1≤T≤1414213562)次，才能达到加密效果．” 这回轮到奶牛们惊呆了．很显然，奶牛们特别讨厌做同样的无聊的事情很多次．经过了漫长的争论，卡门和奶牛们终于找到的解决办法：你被刚来加密这些数字．
Input
第1行输入N和T，之后N行每行一个整数表示初始的Ci．
Output
共N行，每行一个整数，表示T次加密之后的Ci．
Sample Input
3 4
1
0
4
INPUT DETAILS:
Three cows, with starting numbers 1, 0, and 4; four repetitions of the
encryption algorithm.
1
0
4
INPUT DETAILS:
Three cows, with starting numbers 1, 0, and 4; four repetitions of the
encryption algorithm.
Sample Output
26
25
29
OUTPUT DETAILS:
The following is a table of the cows' numbers for each turn:
Cows' numbers
Turn Cow1 Cow2 Cow3
0 1 0 4
1 4 5 1
2 6 5 9
3 14 15 11
4 26 25 29
25
29
OUTPUT DETAILS:
The following is a table of the cows' numbers for each turn:
Cows' numbers
Turn Cow1 Cow2 Cow3
0 1 0 4
1 4 5 1
2 6 5 9
3 14 15 11
4 26 25 29
HINT
N<=50000
Source
Gold
矩阵快速幂+思路~
直接上手写了个n^2的，然后发现n<=50000妥妥的炸掉……
所以无论是空间还是时间都无法承受n^2的复杂度，所以我们必须压缩。
显然n^2有很多状态是没有用的，有用的只是n*2的矩阵。我们把矩阵修改成（tot为所有数总和）:
a1 tot
a2 tot
...
an tot
然后发现这个矩阵是没法自乘的（乘出来也不对），所以我们建立一个小矩阵:
-1 0
1 n-1
大小矩阵相乘一次，显然左面一列是更新后的a1，a2，...，an，右面一列是更新后的tot。
——相乘一次就等价于计算一次。
所以我们就用大的矩阵乘上小矩阵的m次方，这里可以用快速幂优化~
#include<cstdio>
#define ll long long
#define modd 98765431ll n,m,tot;struct node{ll a[50001][3];
}a,c;ll read()
{ll totnum=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {totnum=(totnum<<1)+(totnum<<3)+ch-'0';ch=getchar();}return totnum*f;
}node cheng(node u,node v,int x,int y,int z)
{node az;for(int i=1;i<=x;i++)for(int j=1;j<=y;j++){az.a[i][j]=0;for(int k=1;k<=y;k++) az.a[i][j]=(az.a[i][j]+u.a[i][k]*v.a[k][j])%modd;}return az;
}int main()
{n=read();m=read();a.a[1][1]=-1;a.a[1][2]=0;a.a[2][1]=1;a.a[2][2]=n-1;for(int i=1;i<=n;i++)for(int j=1;j<=2;j++)if(i==j) c.a[i][j]=1;else c.a[i][j]=0;while(m){if(m&1) c=cheng(c,a,2,2,2);a=cheng(a,a,2,2,2);m>>=1; }for(int i=1;i<=n;i++) a.a[i][1]=read()%modd,tot=(tot+a.a[i][1])%modd;for(int i=1;i<=n;i++) a.a[i][2]=tot;a=cheng(a,c,n,2,2);for(int i=1;i<=n;i++) printf("%lld\n",(a.a[i][1]%modd+modd)%modd);return 0;
}