http://www.spoj.pl/problems/SUMSUMS/
最近在做USACO以前的月赛题备战NOIP哎。。。
这道是2007 CHN的。。
琢磨一下可以发现对于每个人来说。。S是所有Ci的总和
任何次数下他的值都是A*S+B*Ci。。且这个A和B只要给定了次数，跟i是无关的。。
可以导出A和B的递推式：
A’=(n-1)*A+B;
B’=-B;
。。但是T太大了。。只好用矩阵乘法加速了。。。
矩阵为
n-1 1
0    -1
Code。。。
#include<iostream>
#include<cstring>
#include<cstdio>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long Board[2][2];
const int maxn=50000;
const long long Mod=98765431;
int N;
long long T;
int C[maxn];
struct Matrix
{
Board own;       
Matrix(){memset(own,0,sizeof(own));}
Matrix operator*(const Matrix&x)
{
Matrix now;
REP(i,2) REP(j,2)
{
REP(k,2)now.own[i][j]+=(own[i][k]*x.own[k][j])%Mod;
now.own[i][j]%=Mod;if(now.own[i][j]<0) now.own[i][j]+=Mod;
}
return now;
}
long long* cal(int A[])
{
long long* ans=new long long[2];
ans[0]=ans[1]=0;
REP(i,2) REP(j,2)
ans[i]+=own[i][j]*A[j];
return ans;
}
void operator=(const Matrix&x)
{
memmove(own,x.own,sizeof(own));
}
}ans,orig;
Matrix power(long long t)
{
if(t==1)   
{
return orig;
}
Matrix now;   
now=power(t/2);
now=now*now;
if(t%2==1)
now=now*orig;
return now;
}
int main()
{
cin>>N>>T;int S=0;
REP(i,N) {scanf("%d",C+i);S+=C[i];S%=Mod;}
orig.own[0][0]=N-1;orig.own[0][1]=1;
orig.own[1][0]=0;orig.own[1][1]=-1;
ans=power(T);
int A[2]={0,1};
long long*get=ans.cal(A);
REP(i,N)
{
long long t=get[0]*S+get[1]*C[i];
t%=Mod;
printf("%lldn",t);
}
}