http:\/\/www.spoj.pl\/problems\/SUMSUMS\/
\u6700\u8fd1\u5728\u505aUSACO\u4ee5\u524d\u7684\u6708\u8d5b\u9898\u5907\u6218NOIP\u54ce\u3002\u3002\u3002
\u8fd9\u9053\u662f2007 CHN\u7684\u3002\u3002
\u7422\u78e8\u4e00\u4e0b\u53ef\u4ee5\u53d1\u73b0\u5bf9\u4e8e\u6bcf\u4e2a\u4eba\u6765\u8bf4\u3002\u3002S\u662f\u6240\u6709Ci\u7684\u603b\u548c
\u4efb\u4f55\u6b21\u6570\u4e0b\u4ed6\u7684\u503c\u90fd\u662fA*S+B*Ci\u3002\u3002\u4e14\u8fd9\u4e2aA\u548cB\u53ea\u8981\u7ed9\u5b9a\u4e86\u6b21\u6570\uff0c\u8ddfi\u662f\u65e0\u5173\u7684\u3002\u3002
\u53ef\u4ee5\u5bfc\u51faA\u548cB\u7684\u9012\u63a8\u5f0f\uff1a
A’=(n-1)*A+B;
B’=-B;
\u3002\u3002\u4f46\u662fT\u592a\u5927\u4e86\u3002\u3002\u53ea\u597d\u7528\u77e9\u9635\u4e58\u6cd5\u52a0\u901f\u4e86\u3002\u3002\u3002
\u77e9\u9635\u4e3a
n-1 1
0 -1
Code\u3002\u3002\u3002
#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);
}
}<\/p>\n","protected":false},"excerpt":{"rendered":"
http:\/\/www.spoj.pl\/problems\/SUMSUMS\/\u6700\u8fd1\u5728\u505aUSACO\u4ee5\u524d\u7684\u6708\u8d5b\u9898\u5907\u6218NOIP\u54ce\u3002\u3002\u3002\u8fd9\u9053\u662f2007 CHN\u7684\u3002\u3002\u7422\u78e8\u4e00\u4e0b\u53ef\u4ee5\u53d1\u73b0\u5bf9\u4e8e\u6bcf\u4e2a\u4eba\u6765\u8bf4\u3002\u3002S\u662f\u6240\u6709Ci\u7684\u603b\u548c\u4efb\u4f55\u6b21\u6570\u4e0b\u4ed6\u7684\u503c\u90fd\u662fA*S+B*Ci\u3002\u3002\u4e14\u8fd9\u4e2aA\u548cB\u53ea\u8981\u7ed9\u5b9a\u4e86\u6b21\u6570\uff0c\u8ddfi\u662f\u65e0\u5173\u7684\u3002\u3002\u53ef\u4ee5\u5bfc\u51faA\u548cB\u7684\u9012\u63a8\u5f0f\uff1aA’=(n-1)*A+B;B’=-B;\u3002\u3002\u4f46\u662fT\u592a\u5927\u4e86\u3002\u3002\u53ea\u597d\u7528\u77e9\u9635\u4e58\u6cd5\u52a0\u901f\u4e86\u3002\u3002\u3002\u77e9\u9635\u4e3an-1 10 -1Code\u3002\u3002\u3002#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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/22"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=22"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/22\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=22"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=22"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=22"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}