首页 > 其他 > 详细

[BZOJ3583]杰杰的女性朋友(矩阵快速幂)

时间:2018-02-19 11:12:24      阅读:257      评论:0      收藏:0      [点我收藏+]

杰杰的女性朋友

时间限制:10s      空间限制:256MB

题目描述

   杰杰是魔法界的一名传奇人物。他对魔法具有深刻的洞察力,惊人的领悟力,以及令人叹为观止的创造力。自从他从事魔法竞赛以来,短短几年时间,就已经成为 世界公认的实力最强的魔法选手之一。更让人惊叹的是,他几乎没有借助外界力量,完全凭借自己的努力达到了普通人难以企及的高度。在最近的世界魔法奥林匹克 竞赛上,他使用高超的魔法本领,一路过关斩将,在最后时刻一举击败了前冠军“旅行者”,获得了魔法界最高的荣耀:女神奖杯!女神奖杯可不是一个普通的奖 杯,她能够帮杰杰实现一个愿望。
  杰杰本着实事求是的态度,审时度势,向女神奖杯提出了自己的愿望:想要一个女性朋友。

  杰杰的愿望实现了,可是女性朋友却和他不在一个城市。杰杰想要知道:如果要到达女性朋友的所在城市,有多少种方案供他选择?
  杰杰所在的世界有n个城市,从1到n进行编号。任意两个城市都通过有向道路连接。每个城市u有k个入点权:in[u][1],in[u] [2]...in[u][k],有k个出点权:ou[u][1],ou[u][2]...ou[u][k]。对于任意两个城市(u,v)(u可以等于 v),u到v的道路条数为(ou[u][1]*in[v][1]+ou[u][2]*in[v][2]+...+ou[u][k]*in[v][k]) 条。杰杰有m次询问,每次询问由三元组(u,v,d)构成,询问从u城市通过不超过d条道路到达v城市的方案数。
  为了温柔的杰杰和他的女性朋友的美好未来,帮助他解答这个问题吧。


输入格式

  第一行读入两个正整数n,k,含义如题所示。接下来n行每行2k个整数,第i行代表第i个城市,前k个整数代表i号城市的出点权,后k个整数代表i号城市的入点权:
  ou[i][1],ou[i][2],…,ou[i][k],in[i][1],in[i][2],…,in[i][k]
  接下来一个整数m,表示m个询问。
  接下来m行,每行三个整数:u,v,d,询问从u城市通过不超过d条道路到达v城市的方案数。
  将每个方案所经过的道路,按顺序写成一个序列(序列可以为空)。两个方案不同,当且仅当他们的道路序列不完全相同。


输出格式


  对于每个询问,输出一个方案数。由于答案可能太大,输出其除以1000000007后的余数。


样例输入

5 2
2 5 4 3
7 9 2 4
0 1 5 2
6 3 9 2
2147483647 1000000001 233522 788488
10
1 1 0
2 2 1
2 4 5
4 3 10
3 4 50
1 5 1000
3 5 1000000000
1 2 500000000
4 5 2147483647
3 1 2147483647

样例输出

1
51
170107227
271772358
34562176
890241289
8516097
383966304
432287042
326522835

提示

数据规模和约定
n<=1000
k<=20
m<=50

  保证1<=u, v<=n, 其它所有读入为不超过2147483647的非负整数


题目来源

By 佚名提供

 FJOI2018一试就是直接使用了这道清华集训原题。

首先列出DP状态转移方程,$f[t][i]$表示走了$t$步之后到达$i$节点的方案数:$$f[t][i]=\sum\limits_{j=1}^{n} (f[t-1][j]*\sum\limits_{l=1}^{k} O_{j,k}*I_{i,l})$$

这样做的复杂度是$O(n^2*d),而 $d \leqslant 2^{31}-1$,显然无法在时限内出解。

观察这个转移方程,不难看出这是裸的矩阵快速幂,于是可以在$O(n^3*\log d)$时间内出解。

然而这个复杂度仍然不够优,事实上,连FJOI2018现场最低的一档部分分都无法通过。

于是需要进一步观察矩阵的性质:

$f$是一个$1*n$的矩阵,$O$是一个$n*k$的矩阵,$I$是$n*k$的,而$C=OI^T$所以$C$是$n*n$的。由数据范围可知,如果我们能将$n*n$的矩阵乘法优化到$k*k$,那么就可以通过全部数据。

不难发现答案$f[d]=f[0]*C^d=f[0]*(OI^T)^d=f[0]*O*(I^T*O)^{d-1}*I$,而$(I^T*O)$是$(k*k)的,所以我们只要求$(I^T*O)$就好了。

 

[BZOJ3583]杰杰的女性朋友(矩阵快速幂)

原文:https://www.cnblogs.com/HocRiser/p/8453579.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!