CF傳送門

洛谷傳送門

【題目分析】

在zxy大佬的講解下終于懂了這道題的做法了qwq。。。

首先根據題意，出發點不一定在特殊點上，但第一次操作后，之后所有的操作都是在特殊點上，所以先考慮從線上出發的最大概率，再加一步即可得到從點出發的最大概率，二者取較大值即可。

記數組f[i][j][k]表示從i點走k步到j點的概率，所以轉移方程就出來了：

然后發現這個形式其實就是矩陣乘法，所以可以利用矩陣快速冪優化，計算出走2^i步的概率。

但每次都進行一次快速冪的計算復雜度為O(n^3log(q))，所以繼續優化。

因為我們只需要考慮最后到達t的最大概率，所以在進行矩陣乘法的時候很多位置都是沒用的，所以考慮將初始矩陣簡化為一個1*n的矩陣，表示走0步到達t的概率，顯然只有base[t]=1，其他位置均為0。

然后將操作數進行二進制拆分進行左乘，因為初始矩陣只有1行，所以不管乘幾次都只有一行，這樣直接優化了一個n的復雜度。

從直線開始就是比從點開始少了一步（因為要先走到點上），所以就先處理從直線開始走的情況統計答案，最后再計算一次就可以得到從點開始走的概率。

考慮構造f[i][j][0]，顯然從i點走一步到達j點的概率為(1/(經過i點直線數)*（直線i,j上的點數）)，根據這個構造即可。

然后就是各種小細節。。。

1.直線去重，這樣可以避免進行重復計算。

2.將一個vector的值賦給另一個vector的時候加個傳址符會快一點。

3.在計算f數組和base數組的時候如果f[i][j][k]或g[i]已經小于1e-6了，那么其實并沒有必要繼續計算下去了，因為精度太小反而可能會爆炸，而且題目也說了誤差在1e-6以內即可，這樣大大減少運行時間。

【代碼~】

#include<bits/stdc++.h> using namespace std; const int MAXN=201; const int MAXM=15;int n,q; int x[MAXN],y[MAXN]; int vis[MAXN],cnt[MAXN]; double ans; double f[MAXN][MAXN][MAXM+1]; double Base[MAXN],zy[MAXN]; vector<int> point[MAXN][MAXN]; vector<pair<int,int> > line; inline int Read(){int i=0,f=1;char c;for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());if(c=='-')f=-1,c=getchar();for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';return i*f; }bool check(int a,int b,int c){return (y[b]-y[a])*(x[c]-x[a])==(y[c]-y[a])*(x[b]-x[a]); }int main(){n=Read();for(int i=1;i<=n;++i)x[i]=Read(),y[i]=Read();for(int i=1;i<=n;++i){memset(vis,0,sizeof(vis));for(int j=1;j<=n;++j){if(i==j)continue;if(vis[j])continue;cnt[i]++;for(int k=1;k<=n;++k){if(check(i,j,k)){point[i][j].push_back(k);vis[k]=1;}}line.push_back(make_pair(point[i][j][0],point[i][j][1]));}}sort(line.begin(),line.end());line.erase(unique(line.begin(),line.end()),line.end());int siz1=line.size();for(int i=0;i<siz1;++i){vector<int> &vec=point[line[i].first][line[i].second];int siz2=vec.size();for(int j=0;j<siz2;++j){for(int k=0;k<siz2;++k){f[vec[j]][vec[k]][0]+=1.0/siz2*1.0;}}}for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){f[i][j][0]/=cnt[i];}}for(int i=1;i<=MAXM;++i){for(int j=1;j<=n;++j){for(int k=1;k<=n;++k){if(f[j][k][i-1]>1e-6){for(int t=1;t<=n;++t){f[j][t][i]+=f[j][k][i-1]*f[k][t][i-1];}}}}}q=Read();while(q--){int t=Read(),step=Read()-1;memset(Base,0,sizeof(Base));Base[t]=1;for(int i=0;i<=MAXM;++i){if((1<<i)>step)break;if((1<<i)&step){memset(zy,0,sizeof(zy));for(int j=1;j<=n;++j){if(Base[j]>1e-6){for(int k=1;k<=n;++k){zy[k]+=f[k][j][i]*Base[j];}}}memcpy(Base,zy,sizeof(zy));}}ans=0.0;int siz=line.size();for(int i=0;i<siz;++i){vector<int> &vec=point[line[i].first][line[i].second];double tot=0.0;int siz2=vec.size();for(int j=0;j<siz2;++j){tot+=Base[vec[j]];}tot/=1.0*siz2;ans=max(ans,tot);}memset(zy,0,sizeof(zy));for(int i=1;i<=n;++i){if(Base[i]>1e-6){for(int j=1;j<=n;++j){zy[j]+=Base[i]*f[j][i][0];}}}memcpy(Base,zy,sizeof(zy));for(int i=1;i<=n;++i)ans=max(ans,Base[i]);printf("%.10lf\n",ans);}return 0; }

?

轉載于:https://www.cnblogs.com/Ishtar/p/10010705.html

總結

以上是生活随笔為你收集整理的CF989E A Trance of Nightfall（概率+矩阵快速幂优化+倍增）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。