【题意】
一个n个位置的环,每经过一次置换,每个位置的值会变成上一次周围d范围之内的和,求mod m后置换过k次后每个位置的值
【输入】
第一行n、m、d、k
第二行n个数,表示n个数的初始值
【输出】
输出n个数表示经过k次置换后,每个位置的值
很容易可以看出是矩阵乘法
n<=500
如果构建n*n的矩阵,矩阵乘法复杂度为n^3,那么总体复杂度为n^3log k 是不能接受的
但是可以发现一个矩阵的性质
因为是求d范围之内之和,所以矩阵每一行基本一样,只是错了一位而已
所以求矩阵的时候只需要求一行就够了,复杂度降到n^2,便可以通过了
program poj3150; type arr=array [0..501] of int64; var d,m,n,i,j,k:longint; sum:int64; h:array [0..501] of int64; ans,root:arr; function convert (now:longint):longint; begin now:=now mod n; if now=0 then exit(n) else exit(now); end; function multiply (a,b:arr):arr; var i,j,k:longint; ans:arr; begin fillchar(ans,sizeof(ans),0); for i:=1 to n do for j:=1 to n do ans[i]:=(ans[i]+a[j]*b[convert(i+j-1)]) mod m; exit(ans); end; procedure quick (now:longint); begin if now=1 then begin ans:=root; exit; end; quick(now div 2); ans:=multiply(ans,ans); if now and 1 = 1 then ans:=multiply(ans,root); end; begin read(n,m,d,k); for i:=1 to n do read(h[i]); for i:=1 to d+1 do root[i]:=1; for i:=n-d+1 to n do root[i]:=1; quick(k); for i:=1 to n do begin sum:=0; for j:=1 to n do sum:=(sum+h[convert(i+j-1)]*ans[j]) mod m; write(sum,' '); end; writeln; end.