首页 > 代码库 > BZOJ2326: [HNOI2011]数学作业
BZOJ2326: [HNOI2011]数学作业
2326: [HNOI2011]数学作业
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 955 Solved: 535
[Submit][Status]
Description
.jpg)
题解：
第一次知道矩阵乘法还能这样用，真是太神了！
我想到了递推式：
f[i]=(f[i-1]*10^len[i]+i) mod p
但是我没有办法用矩阵乘法来解决这样 f[i]=a*f[i-1]+b 但a和b都随着 i 的变化而变化
可以分位数来消掉a的变化，但是b我无法解决。
看了题解之后发现居然还可以这样！
把矩阵增一维
(f[i-1],i-1,1)*(10^len(i),0 0 =(f[i],i,1)
1,1,0
1,1,1)
简直太神了！原来矩阵不仅可以快速求解 线性递推式，还可以求解这样的，只要把变化的量一同加入矩阵的表示中即可。
题外话：
不会写 c++ 的矩阵快速幂，只好上pascal了。。。
边界要注意，想清楚了再写。
矩阵满足结合律，不满足交换律。
代码：
1 type matrix=array[1..3,1..3] of int64; 2 var a,b,c:matrix; 3 m:array[0..18] of int64; 4 i,j:longint; 5 cs,n,p:int64; 6 s:string; 7 operator *(a,b:matrix)c:matrix; 8 var i,j,k:longint; 9 begin10 fillchar(c,sizeof(c),0);11 for i:=1 to 3 do12 for j:=1 to 3 do13 for k:=1 to 3 do14 c[i,j]:=(c[i,j]+(a[i,k]*b[k,j] mod p)) mod p;15 end;16 procedure main;17 begin18 m[0]:=1;19 for i:=1 to 18 do m[i]:=m[i-1]*10;20 readln(n,p);str(n,s);21 fillchar(b,sizeof(b),0);22 for i:=1 to 3 do b[i,i]:=1;23 for i:=1 to length(s) do24 begin25 if i<>length(s) then cs:=m[i]-m[i-1] else cs:=n-m[length(s)-1]+1;26 a[1,1]:=m[i] mod p;a[1,2]:=0;a[1,3]:=0;27 a[2,1]:=1;a[2,2]:=1;a[2,3]:=0;28 a[3,1]:=1;a[3,2]:=1;a[3,3]:=1;29 while cs>0 do30 begin31 if cs and 1=1 then b:=b*a;32 cs:=cs>>1;33 a:=a*a;34 end;35 end;36 writeln(b[3,1]);37 end;38 39 begin40 assign(input,‘input.txt‘);assign(output,‘output.txt‘);41 reset(input);rewrite(output);42 main;43 close(input);close(output);44 end.
BZOJ2326: [HNOI2011]数学作业
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。