矩阵经典题……

支持魔兽！支持暗夜精灵！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

100题纪念。

原来想是一个o(n)的dp

f[i]=2*f+f;

看了题解后才知道原来矩阵可以这样玩= =。

给几个数据让后人参考

3 10

ans：274

10 10000000

ans：7258941

= =

原来矩阵乘法是这样用的

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

第415

初学矩阵

继续努力

第410人通过...

快速幂竟然有一句写错了...没有体验到1A的感觉...

强大的矩阵乘法...

program warden;

type

arr=array[0..11,0..11]of qword;

var

x,s,k,n:int64;

i,j,l,tt:longint;

a,aa:arr;

procedure doit(a:arr;var b:arr;t:longint);

var

c,d,e:arr;

i,j,q,p:longint;

begin

d:=a;

for q:=1 to t do

begin

fillchar(c,sizeof(c),0);

for i:=1 to k do

for j:=1 to k do

begin

for p:=1 to k do

c:=c+d*d[p,j];

c:=cmod 7777777;

end;

d:=c;

end;

if x=1 then begin b:=c;exit;end;

d:=b;

fillchar(e,sizeof(e),0);

for i:=1 to k do

for j:=1 to k do

begin

for p:=1 to k do

e:=e+d*c[p,j];

e:=e mod 7777777;

end;

b:=e;

end;

begin

readln(k);

readln(n);

fillchar(aa,sizeof(aa),0);

fillchar(a,sizeof(a),0);

for I:=1 to k do

aa[1,i]:=1;

j:=1;

for i:=2 to k do

begin

aa:=1;

inc(j);

end;

x:=0;

repeat

l:=0;

tt:=1;

while tt

一次秒杀，第401人通过。

看了Matrix67大牛的矩阵后才来做的这道题。

ORZ Matrix67大牛

---|---|---|---|---|---|---|---|--

Flag 　　Accepted

题号 　　P1067

类型(?) 　　数论 / 数值

通过 　　401人

提交 　　1562次

通过率 　　26%

难度 　　3

---|---|---|---|---|---|---|---|---|---|

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

郁闷啊

例如 F[N]=A*F[N-3]+B*F[N-2]+C*F[N-1]的递推式、可以用矩阵乘

构造：

0 1 0 F[1] F[2]

0 0 1 * F[2] =F[3]

A B C F[3] A*F[1]+B*F[2]+C*F[3](就是F[4])

(PS:ORZ tobright大牛)

传统魔兽么兴趣类、、我玩DOTA的、志同道合的同学加我的DOTA群哦、

32043570、灼热大地`灬.闪耀、

菜鸟、神鸟都欢迎、

Program war;

type

arr=array[0..11,0..11] of int64;

var

i,j,k,l,m,n :longint;

a :arr;

非得这么小的数组不可,否则递归调用多了就内存崩溃,产生253错误,大家注意下

强大的矩阵

get it.

原来矩阵可以这么用。哈哈。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0m

Warden 居然用不好...

与人族PK中...

编译通过...

├ 测试数据 01：搜索评测机中... 32723ms

├ 测试数据 02：Vivid Puppy评测机故障... 34223ms

├ 测试数据 03：Vijos Dragon评测机故障... 3999ms

├ 测试数据 04：Vag 6K评测机故障... 1234ms

├ 测试数据 05：Vijos Dolphin评测机故障... 142ms

├ 测试数据 06：Viking Mew评测机故障... 32323ms

├ 测试数据 07：Viajaca Fish评测机故障... 32201ms

├ 测试数据 08：Victoria Roo评测机故障...4321ms

├ 测试数据 09：Vaal Leopard评测机故障... 429421ms

├ 测试数据 10：Venus Blaze评测机故障... 142ms

├ 测试数据 11：紫田漯河双线机房跳电... 1ms

├ 测试数据 12：vijos.cn正式瘫痪... 1ms

---|---|---|---|---|---|---|---|-

unaccepted 有效得分：0 有效耗时：560731ms

竟然被我一遍AC。。难得诶。。

给后来人一个比较完整的题解版本吧：

首先是如何构造这个矩阵：

右上角是一个(n-1)*(n-1)的单位矩阵，最底下一行是线性递推式各项的系数；

以下是构造矩阵的核心代码：

procedure make_matrix;

var i:longint;

begin

fillchar(a,sizeof(a),0); a[k,k]:=1;

for i:=1 to k-1 do

begin

a:=1;

a[k,i]:=1;

end;

end;

接着是如何进行矩阵乘法：

设A*B=C，则有C=sigma(A+B[k,j])

以下是矩阵相乘的核心代码：

function mul(a,b:mat;m,n,p:longint):mat;

var i,j,t:longint;

begin

fillchar(mul,sizeof(mul),0);

for i:=1 to m do

for j:=1 to p do

for t:=1 to n do

inc(mul,a*b[t,j]);

end;

然后是如何做快速幂：

这里提供一个经典的矩阵快速幂（同楼下tracy大牛）：

function power(a:mat;n:longint):mat;

var t:mat;

begin

if n=1 then exit(a);

t:=power(a,n shr 1);

t:=mul(t,t,k,k,k);

if n and 1=1 then t:=mul(t,a,k,k,k);

exit(t);

end;

由于本题递推式为f[n]=sigma(f[n-i]),1

http://www.matrix67.com/blog/archives/276

用int64=ac...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

矩阵乘法。

膜拜cai0715神牛！

恩，８错８错，矩阵求递推通项会了！！！！

纠结啊，忘记了可以n < k 的了