1
#include<iostream>
2using namespace std;
3#define M 98765431
4#define Max_N 50000
5int N,T,sum=0;
6int cows[Max_N];
7int t[32];
8__int64 a,b;
9int D_to_B(int x)
10{
11 int i=0;
12 while(x>=1){
13 t[i++]=x%2;
14 x/=2;}
15 return i;
16}
17void Multi(__int64 a[2][2],__int64 b[2][2])//矩陣a*b
18{
19 __int64 c[2][2];
20 int i,j,h;
21 memset(c,0,sizeof(c));
22 for(i=0;i<2;i++)
23 for(j=0;j<2;j++)
24 for(h=0;h<2;h++){
25 c[i][j]+=M+a[i][h]*b[h][j];//防止c[i][j]<0的情況
26 c[i][j]%=M;}
27 for(i=0;i<2;i++)
28 for(j=0;j<2;j++)
29 a[i][j]=c[i][j];
30}
31void Multi_k(__int64 a[2][2],int x)//a^x
32{
33 int k,i,j;
34 __int64 temp[2][2]={1,0,0,1};
35 k=D_to_B(x);//把x轉為二進制
36 for(i=k-1;i>=0;i--){
37 Multi(temp,temp);
38 if(t[i]==1)Multi(temp,a);
39 }
40 for(i=0;i<2;i++)
41 for(j=0;j<2;j++)
42 a[i][j]=temp[i][j];
43}
44void compute_ab()
45{
46 __int64 A[2][2]={N-1,0,1,-1};
47 if(T==1){a=0;b=1;return;}
48 Multi_k(A,T-2);//求bT-1的一步,A^T-2
49 b=(A[1][0]*(N-1)+A[1][1])%M;//這是bT-1，用來求aT的，aT=(N-1)*bT-1
50 a=((N-1)*b)%M;
51 b=(A[1][0]*(N-1)*(N-1)+A[1][1]*(N-2))%M;//利用bT-1求bT
52}
53void solve()
54{
55 int i;
56 __int64 sum_i,result;
57 for(i=0;i<N;i++){
58 sum_i=(sum+M-cows[i])%M;//sum除了第i頭牛
59 result=(b*sum_i+a*cows[i])%M;
60 printf("%I64d\n",result);}
61}
62int main()
63{
64 /*freopen("1.in","r",stdin);
65 freopen("3.ans","w",stdout);*/
66 int i;
67 scanf("%d%d",&N,&T);
68 compute_ab();
69 for(i=0;i<N;i++){
70 scanf("%d",&cows[i]);
71 cows[i]%=M;
72 sum+=cows[i];
73 sum%=M;}
74 solve();
75 return 0;
76}
77
posted on 2008-03-05 17:03
zoyi 閱讀(213)
評論(0) 編輯 收藏 引用 所屬分類:
acm