检测智商
校赛中的一道神仙题,难点不在算法或者特别的技巧,专杀惯性思维
luoguT319422 穷哥们也想发财
https://www.luogu.com.cn/problem/T319422
题意:已知列向量A,矩阵P,变量K,其中矩阵P满足对于j,有 $\sum^n a_{i,j}=1,a_i\in(0,1) .$. 求出 $ B=(P^T)^k*A $. ,其中$P^T$代表P的转置矩阵
数据范围: $ n\in (1,7e2),K\in(1,1e10) $
乍一看就是矩阵快速幂的模板,几乎不能更简单.
然而略加分析或者tle了一发可以发现,一般的矩乘快速幂,复杂度$O(n^3logK)$,在本题的数据大概能达到1e9级别,甚至做一次矩乘,都要大概3e8次运算,在double乘法的大常数下,只乘一次都会超时.
回看题目,发现有一个条件没有用到, $ \sum^n a_{i,j}=1,a_i\in(0,1) .$. 这个条件可以满足在自乘若干次后,矩阵P的内容趋于稳定,性质的证明涉及马尔科夫链.
于是就采用最原始的办法去做,不断的用P左乘A,比较A是否达到不动点.这个次数似乎与P的分布有关,不过应该不会太大,可以通过本题.
另外出题人特意提醒了用double,long double反而会有精度问题