题解 P2100 【凌乱的地下室】

· · 题解

(题目给了双倍时间空间..)..

题意.给出n个数.每个数的位置可能移动.但只可能移动到原位置+1或-1.求不同序列的总数..

可以看出.这是1个交换过程..且每个数最多只能被交换1次...(除非反复交换..)..

拿来P1962程序跑了跑样例..果然是的..

下面给出伪证明..

设f[i]为前i位可能组成不同序列的数量.
将f[i]拆分.
f[i,1]表示第i个数与第i-1个数交换后,有多少不同序列.
f[i,2]表示第i个数与第i-1个数不交换,有多少不同的序列..
显然有.f[i] = f[i,1]+f[i,2];
如果交换.第i-1个数不能再被其他的数交换..有f[i,1] = f[i-1,2];
没有交换.不产生影响.f[i,2] = f[i-1,1]+f[i-1,2];
接下来.
f[i,1] = f[i-1,2] = f[i-2,1]+f[i-2,2] = f[i-2];
f[i,2] = f[i-1,1]+f[i-1,2] = f[i-1];
f[i] = f[i,1]+f[i,2] = f[i-2]+f[i-1] = f[i-1]+f[i-2];

所以这就是个Fibonacci....

若你过了P1962,或者会矩阵乘法.大概就能过了..

我的构造方法:

1 1   1 1 ^(n-1)
    *(   )       mot 100000000.
0 0   1 0
 a     b
ans = a[1,1].

题目说只给0.2s..(其实是0.4s.)..

于是跑到P4000补了补循环节求法..请至P4000题解查看....

(懒得写..)..

经过计算.本题可以转化成:

先将n对150000000取模,用矩阵乘法求Fibonacci第n+1项对100000000取模...

丢代码..太乱的话建议去掉//并分开子程序..

其实建议不要看...

program P2100;
 type
  ws=record
   fc:array[1..2,1..2] of int64; //矩阵.
   x,y:longint;
  end;
  wc=record                      //就是个字符换数字的东西..
   case integer of
    1:(c:char);
    2:(d:byte);
  end;
 var
  a,b,c,d:ws;
  cc:wc;
  mot,mots,p:int64;
 function hahainf(p:int64):int64;forward;
 function hahafff(x:int64):int64;forward;
 function hahaggb(P:int64):int64;forward;
 operator **(x,y:int64)z:int64;  //快速幂..
  begin
   z:=1;
   while y>0 do
    begin
     if y and 1=1 then z:=z*x mod mot;
     x:=x*x mod mot;
     y:=y>>1;
    end;
  end;
 operator *(x,y:ws)z:ws;         //矩乘.
  var
   i,j,k:longint;
  begin
   fillqword(z,sizeof(z)>>3,0);
   z.x:=x.x;
   z.y:=y.y;
   for i:=1 to x.x do
    for j:=1 to y.y do
     for k:=1 to x.y do
      z.fc[i,j]:=(z.fc[i,j]+x.fc[i,k]*y.fc[k,j]) mod mot;
  end;
 function hahagcd(x,y:int64):int64;   //求gcd..
  begin
   if x<y then exit(hahagcd(y,x));
   if y=0 then exit(x);
   exit(hahagcd(y,x mod y));
  end;
 function hahaha(p:int64):int64;         //用来求循环节.
  var
   i:longint;
   x,y:int64;
  procedure hahax(var p:int64;i:int64);  //请出门至P4000.
   begin
    y:=p div i;
    x:=hahaggb(i);
    while p mod i=0 do p:=p div i;
    x:=x*y div p;                           //g(i)*i^(m-1);
    hahaha:=hahaha div hahagcd(hahaha,x)*x; //求lcm...
   end;
  begin
   hahaha:=1;
   for i:=2 to trunc(sqrt(p)) do         //对膜值分解..
    if p mod i=0 then hahax(p,int64(i));
   if p>1 then hahax(p,p);
  end;
 function hahaggb(p:int64):int64;        //请出门至P4000.
  var
   ffiu:array[0..5] of longint=(0,1,3,8,6,20);
  begin
   if (p<=5) then exit(ffiu[p]);
   if 5**((p-1)>>1)=1 then exit(hahainf(p-1))      //欧拉准则.??
                      else exit(hahainf((p+1)<<1)); /x^((p-1)>>1) = 1.
   //writeln(5**((p-1)>>1)=1);
   //exit(hahainf((p+1)<<1));
  end;
 function hahainf(p:int64):int64;         //此处本应该求约数..
  begin                                    /由于1E+08 = 2^8*5^8;
   //if hahafff(f[i]+4)=3 then exit(f[i]); /也就没用了..
   //exit(5882353);
  end;
 function hahafff(x:int64):int64;         //矩阵快速幂..
  begin
   while x>0 do
    begin
     if x and 1=1 then a:=a*b;
     x:=x>>1;
     b:=b*b;
    end;
   hahafff:=a.fc[1,1];
  end;
 procedure haharere;        //初始化..
  begin
   fillchar(d,sizeof(d),0);
   d.x:=2;
   d.y:=2;
   b:=d;
   a:=d;
   b.fc[1,1]:=1;
   b.fc[1,2]:=1;
   b.fc[2,1]:=1;
   a.fc[1,1]:=1;
   a.fc[1,2]:=1;
   a.x:=1;
  end;
 begin
  mot:=100000000;
  //writeln(hahaha(mot));
  mots:=hahaha(mot);       //也可直接赋值为150000000..
  haharere;
  //readln(n);
  //writeln(hahafff(5));
  p:=0;
  while not eoln do
   begin
    read(cc.c);
    //writeln(cc.d);
    p:=(p*10+cc.d-48) mod mots;
   end;
  writeln(hahafff(p-1));   //由于前2项已经在矩阵里..只要乘上n-1项..
 end.

(ಡωಡ).