矩阵快速幂优化dp -E. A Trance of Nightfall（CodeForces989）

传送门

Analysis

好题啊，不会做的都是好题，emmm
dzyo说这道题不是一眼dp吗。。。。。（好吧好吧，那就假设我们知道这道题可以dp搞了，反正我不知道）

由问题：“求连续移动mi步，最后到达ti的最大概率是多少” 可知
我们可以定义状态$A_{i,u,v}$表示从 u 走 i 步到达 v 的概率是多少
最后我们的目标就是$max(A_{mi,x,ti})$( x 是我们一开始选择的起点）
显然我们的转移就是
$$A_{i+1,u,k}=\Sigma (A_{i,u,v}\ast A_{1,v,k})$$
然后我们惊奇地发现这不就是矩阵乘法吗？？？（这个转移形式可以有）
但如果每次询问都乘 mi 次，时间肯定耗不起
怎么办呢？
常见套路 （倍增思想）： 预处理走 1、2、4、8、16……步的矩阵。
这样的话，询问时就是用一个 $1\ast n$ 的矩阵与 log 个$n\ast n$ 的矩阵相乘。

现在来考虑怎么计算A
如果在x 有cnt条直线可供选择，y所在的直线有 num 个点，那么从 x 到y的概率是$\frac{1}{cnt\ast num}$
那我们就先处理出有多少条直线经过点i，得到$cnt[i]$
再处理同一条直线上任意两点互相到达的概率$\frac{1}{num}$‘然后就可以计算任意两点的概率了（选择这条直线的概率*在这条直线上走到这个点的概率）
是不是就完了呀？

不不不，当然不是
我们还没有考虑出发点呢
显然出发点的选择只有两种情况
1.在两个景点构成的直线上取一个点
2.选择景点
那我们分开考虑，再取max即可
注意对于情况1，我们先走mi-1步走到一个景点上去

Code

#include<bits/stdc++.h>
using namespace std;
const int N=300;
int n,x[N],y[N],m;
int cnt[N];
bool vis[N];
double g[N],tmp[N],f[20][N][N];
vector<int> G[N][N];
vector<pair<int,int> > line;
bool judge(int u,int v,int i){//判断i这个点是否在u,v构成的直线上 
	return (x[i]-x[v])*(y[v]-y[u])==(x[v]-x[u])*(y[i]-y[v]);
}
int main(){
	scanf("%d",&n);
	int i,j;	
	for(i=1;i<=n;++i)//读入每一个点 
		scanf("%d%d",&x[i],&y[i]);
	//预处理出每一个点会被多少个直线经过
	for(i=1;i<=n;++i){
		memset(vis,0,sizeof(vis));//如果vis标记为1，则说明当前这个点和i属于同一直线
		for(j=1;j<=n;++j){
			if(vis[j]) continue;
			if(i==j) continue;
			++cnt[i];
			for(int u=1;u<=n;++u)
				if(judge(i,j,u)) G[i][j].push_back(u),vis[u]=1;
			line.push_back(make_pair(G[i][j][0],G[i][j][1]));
		} 
	} 
	
	sort(line.begin(),line.end());
	line.erase(unique(line.begin(),line.end()),line.end());//重边 
	
	for(int i=0;i<line.size();++i){//计算每一条直线上任意两点互相到达的概率 
		vector<int> &vec=G[line[i].first][line[i].second];//写成引用（随手卡常（zxy%%），vector的复制可不是O（1）的啊 
		for(int u=0;u<vec.size();++u)
			for(int v=0;v<vec.size();++v) f[0][vec[u]][vec[v]]+=1.0/(1.0*vec.size());//加等于 
	}
	for(int i=1;i<=n;++i)	//计算走到这条直线的概率 
		for(int j=1;j<=n;++j) f[0][i][j]/=cnt[i];
	for(int i=1;i<=15;++i)//预处理倍增 
	{
		for(int u=1;u<=n;++u)
			for(int v=1;v<=n;++v)
				for(int k=1;k<=n;++k)
			     	f[i][u][v]+=f[i-1][u][k]*f[i-1][k][v];
	}
	scanf("%d",&m);
	for(int t=1;t<=m;++t){
		int goal,stp;
		scanf("%d%d",&goal,&stp);
		stp--;
		memset(g,0,sizeof(g));
		g[goal]=1;//g[i]表示从i走到goal的概率 
		
		for(int i=0;(1<<i)<=stp;++i){//处理每个点往外走stp-1步走到goal的概率 
			if((1<<i)&stp){
				memset(tmp,0,sizeof(tmp));
				for(int u=1;u<=n;++u) if(g[u]>1e-6)
					for(int v=1;v<=n;++v)
						tmp[v]+=f[i][v][u]*g[u];
				memcpy(g,tmp,sizeof(tmp));
			}
		}
		double ans=-1;
		double hh=0;
		for(int i=0;i<line.size();++i){//再计算从每条直线走到其上点的概率 
			hh=0;
			vector<int> &vec=G[line[i].first][line[i].second];
			for(int j=0;j<vec.size();++j) hh+=g[vec[j]];
			hh/=1.0*vec.size();
			ans=max(ans,hh);
		}
		memset(tmp,0,sizeof(tmp));
		for(int u=1;u<=n;++u) if(g[u]>1e-6)//计算每个点往外走stp步走到goal的概率 
			for(int v=1;v<=n;++v)
				tmp[v]+=f[0][v][u]*g[u];
		for(int i=1;i<=n;++i) ans=max(ans,tmp[i]);
		printf("%lf\n",ans); 
	}
	return 0;
}