My December » Blog Archive » 矩阵求前N项K次方和及变形企业库|免费b2b网站

$S(n)(k)=sum{i=1}{n}{i^k} , n in (1 , 10^10) , k in (1 , 100)$ 求 S(n)(k) MOD ~ P
数据量很大,首先想到利用矩阵,但是构造矩阵需要利用递推性质,于是先发掘递推性.
这里为方便起见先设k=4.结论显然可以推广到更大的k.
对于一个数 A^4 ,为了研究它与前项之间的关系,看成 (A-1+1)^4
对其进行二项式分解:
(A-1+1)^4 = (A-1)^4 +~ 4*(A-1)^3 +~6*(A-1)^2 + ~4*(A-1) + ~1
由此可以看出, A^4 与前一项的0次方到4次方有关,于是开始构造矩阵.

先考虑大小为(5 * 1)的矩阵 M_1 : $delim{|} {matrix{5}{1}{ (A - 1)^4 (A-1)^3 (A-1)^2 (A-1)^1 (A-1)^0 } }{|}$
然后在它左边构造一个合适的系数矩阵 M_2 ,使得 M_2 * M_1 得到 $delim{|} {matrix{5}{1}{ A^4 A^3 A^2 A^1 A^0 } }{|}$
由二项式公式可以构造出系数矩阵 M_2 : delim{|} {matrix{5}{5}{ 1 0 0 0 0 1 1 0 0 0 1 2 1 0 0 1 3 3 1 0 1 4 6 4 1 } }{|}
现在能算出的只是 n^k ,那怎么才能算出 S(n)(k) 呢?再看刚才的矩阵 M_1 ,考虑在这里保存一个前n-1的和,于是再添加一行,构造矩阵 M_3 : $delim{|} {matrix{6}{1}{ (A - 1)^4 (A-1)^3 (A-1)^2 (A-1)^1 (A-1)^0 S_{A-1}} }{|}$
要把 $S_{A-1}$ 变成 S_A ,只要把 $S_{A-1}$ 加上 A^k 就可以了.
于是构造系数矩阵 M_4 : delim{|} {matrix{6}{6}{ 1 0 0 0 0 0 1 1 0 0 0 0 1 2 1 0 0 0 1 3 3 1 0 0 1 4 6 4 1 0 1 4 6 4 1 1} }{|}

至此,工作差不多算完成了, S(n)(k) 就是 $(M_4)^n*M_{init}$ 的{zh1}一行那个元素的值, $M_{init}$ 为初始值矩阵.

一个小小的变形,比如这题,具体要求不描述了,请看题目.
一眼看去,一般的思路是先求出总和,再减去不符合要求的部分.这里讲另外一种思路.
再看矩阵 M_4 ,发现如果不想加上某个 A^k ,只要把{zh1}一行除{zh1}一个元素外都设为0即可.
而这题的周期性很明显,7天为一个周期,于是想到把一个周期内的矩阵按顺序乘起来形成新的系数矩阵.然后就容易做了.