GDOI2015DAY1T2粗心的邮差【矩阵乘法】

  • 内容
  • 评论
  • 相关

貌似是我的第一道矩乘题来着。。


题目点击这里

反正我当时看到数据范围以为是O(1)的题来着(完全不知道有个叫矩阵乘法的神奇东西)。


题意还算很好理解,方法在这里说一下

对于40%的数据可以用朴素的状压DP,用f[i,j]表示送完第i封信,第i个位置状态为j的方案数。什么叫状态为j?就是第i个位置附近的5个位置里,收到信的为1,没收到的为0,转成十进制就是j了。最后输出f[n,(11100)2]就是答案。

上面的方法难以通过100%的数据,但我们发现f[i,j]的转移于i无关,也就是每次转移都是固定的,这里就可以想到使用矩乘快速幂搞定。


下面放代码:

肘子:

你为什么要打那个大大的矩阵,反正你直接预处理不就可以了?

有道理。。。我只是没想到嘛。。怎么可能,我怕你们矩阵打错了调不出来于是给出矩阵可以让你们少走点弯路嘛


const
  a:array[0..31,0..31]of int64=((0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0),
                                (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1));
var
  f,ff:array[0..31]of int64;
  t,kk:array[0..31,0..31]of int64;
  i,j,k:longint;
  n:int64;
begin
  read(n);
  f[28]:=1;
  for i:=0 to 31 do
  for j:=0 to 31 do
  t[i,j]:=a[i,j]; 
  repeat
    if n mod 2=1 then
    begin
      fillchar(ff,sizeof(ff),0);
      for i:=0 to 31 do
      for j:=0 to 31 do
      ff[j]:=(ff[j]+f[i]*t[i,j]) mod 1000000007;
      f:=ff;
    end;
    n:=n div 2;
    fillchar(kk,sizeof(kk),0);
    for k:=0 to 31 do
    for i:=0 to 31 do
    for j:=0 to 31 do
    kk[i,j]:=(kk[i,j]+t[i,k]*t[k,j]) mod 1000000007;
    t:=kk;
  until n=0;
  writeln(f[28]);
end.

评论

2条评论
  1. Gravatar 头像

    ws_fqk 回复

    神犇在吗,请问这个表是怎么生成的?
    能留一个qq吗?我的qq317724071

    • Gravatar 头像

      xyyxiao007 回复

      @ws_fqk 这个表可以通过暴力弄出来。。。具体方法就是枚举两个状态i和j,然后暴力判断状态i能不能推出状态j。
      我的QQ是867813290,我来加你吧,我的QQ有验证问题。
      还有,我不是神犇,真的不是。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据