矩阵连乘。每次置换都可以看做乘一个矩阵。如操作 3 1 2 4，

相当于

0 0 1 0 1

1 0 0 0 2

0 1 0 0 乘以 3

0 0 0 1 4

将m操作合并，即按操作顺序连乘，再求最后合并矩阵的（k/m）次方，最后k%m就一一相乘模拟就OK了~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

本来想用这题来练习刚学的矩阵的~~

可是做了才发现根本不用矩阵……

把m次合成一次 做k div m 次（二分快速幂优化）

再最后做k mod m 前个

二分快速幂卡了我好久，矩阵放到递归里面返回把栈给爆了，只好先递归分解幂，然后逐个判断分解的出来数的奇偶，再乘。

最后两点有点慢，懒得位运算了。

编译通过...

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

压缩压缩狂压缩……

虽然没秒杀。。。。

强悍的题...交了7次......

我是个菜油....

有些感想：

1.可以不用矩阵

2.一定用2分

3.可以找循环节

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我弱 矩阵乘法哪个在左边哪个在右边没想清楚。。。糊涂凑对样例。。。糊涂AC。。我若 置换那里没想清楚....

压缩压缩再压缩……直到压缩不下去为止！

大牛们说的太精炼了，我研究了半天

其实只要先做x次，这个x可以设到n*10000

然后记下来做这些次数的结果，后面先做k div x，这时的操作就是记下来的n*10000次的更新结果

再做k mod x 次，按原来的做

不过这样貌似不能0ms

有错的话，请大牛指教

其实直接小倍增就可以0ms

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var aa,ex,tmp,b:array[0..100]of longint;

a:array[0..10,0..100]of longint;

k:int64;

j,circle,n,m,i,tot:longint;

flag:boolean;

procedure make(p:longint);

var i:longint;

begin

tmp:=b;

for i:=1 to m do

b[i]:=tmp[a[p,i]];

end;

begin

readln(m,n,k);

for i:=0 to n-1 do

for j:=1 to m do read(a);

for i:=1 to m do b[i]:=i;

i:=n-1;ex:=b;tot:=0;flag:=false;

while k>0 do

begin

dec(k);

tot:=tot+1;

i:=(i+1)mod n;

make(i);

if tot=10000*n then begin flag:=true;aa:=b;break;end;

end;

if flag then begin

while K>10000*n do

begin

k:=k-10000*n;

tmp:=b;

for j:=1 to m do b[j]:=tmp[aa[j]];

end;

i:=n-1;

while k>0 do

begin

dec(k);

i:=(i+1)mod n;

make(i);

end;

end;

for i:=1 to m-1 do write(b[i],' ');

writeLn(b[m]);

end.

矩阵乘法，不懂看这里吧：

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

编译通过...

全部0ms.

注意到如果对于这m行如果执行的次数足够多，就会回到“1,2,3,...,n”.

本着这条性质，有如下的方案：

①求出执行完m行后的状态，组成置换(1,2,...,n)--(f1,f2,...,fn)（*）

②求出上述置换()的循环周期 T

③x:=(k div m) mod T

④从（1,2,...,n）的状态出发将置换（）执行x次，得到（k1,k2,...,kn）状态

⑤对于(k1,k2,...,kn)执行矩阵的前(k mod m)行，得到新状态（ans1,ans2,...ansn）

⑥输出上述得到的状态

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

快速幂好像慢了点…………

一开始递归忘了回带矩阵的值，0分~~55555555

这道题目是我第一道自己想出来的矩阵乘法题目，其实不是很难

我是用n*n的0，1矩阵表示状态

把每次修改看成是一次矩阵乘法，然后就是快速幂

拥有矩阵的性质所以有结合率

当然不需要矩阵操作即可完成了

struct F

{

int x[101];

F operator *(F u)

{

F t;

for(int i=1;i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第一次做时脑子进水了，居然以为O(k/m)的能过。。40

痛定思痛，上快速幂！ AC~

P.S.矩阵乘法怎么做？。。

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

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

我怎么觉得矩阵是LOG(K/M)*N^3的??没弄清..

反正置换的结合有结合律,直接二分最快

郁闷中间PASCAL卡死

在万分悲痛中,重写,

又把N的范围看成10...

INT64开成了LONGINT...

终于过了...

先把m个操作压缩成一个。再进行加速迭代，（应该就是大家所谓的“倍增”吧。本人一直称之为加速迭代。）此题中运用加速迭代的本质也是压缩。

时间复杂度O(ln(k)/ln(2))，相当好做。

矩阵真好用！！！