欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces 989E A Trance of Nightfall 矩阵快速幂+DP

程序员文章站 2022-07-03 21:43:42
...

改编自Codeforces 989E A Trance of Nightfall 矩阵快速幂+DP

题意:二维平面上右一点集SS,共nn个元素,开始位于平面上任意点PP,PP不一定属于SS,每次操作为选一条至少包含SS中两个元素和当前位置PP的直线,每条直线选取概率相同,同一直线上每个点Q \in SQ∈S 选取概率相同,QQ次询问 包含两个元素t,mt,m 即点PP到tt共操作mm次的最大概率

打了场CFCF 结果DD题死活调不出来 只能一大早来补题了

可以想到记录f[i][j][k]f[i][j][k]表示从点ii到点jj走kk步的概率 这个过程我们可以通过记录2^x2x的矩阵来存储

之后可以发现对于一个询问t,mt,m 我们可以通过矩阵的转移得到走m-1m−1步的答案 之所以不能直接走mm步是因为第一步的点P不一定在SS内 分析一下就可以发现 一条线ll上的点的概率就\frac {\sum_{(i \in S)}probility[i]}{\sum_{(i \in S)}1}∑(i∈S) 1∑(i∈S) probility[i]  对所有直线取个maxmax就是答案了

复杂度 O((n + q) \cdot n^2 \cdot \log m)O((n+q)⋅n2⋅logm)

 

#include<bits/stdc++.h>
using namespace std;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pa pair<int,int>
#define mod 1000000007
#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define cl(x) memset(x,0,sizeof x)
#ifdef Devil_Gary
#define bug(x) cout<<(#x)<<" "<<(x)<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define bug(x)
#define debug(...)
#endif
const int INF = 0x7fffffff;
const int N=2e2+5;
/*
char *TT,*mo,but[(1<<15)+2];
#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin),TT==mo))?-1:*TT++)//*/
inline int read(){
    int x=0,rev=0,ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return rev?-x:x;
}
int n,flg,x[N],y[N];
double ans,pro[N],tmp[N];
vector<vector<int> > lines;
struct matrix{
    double g[N][N];
    matrix operator * (const matrix&a){
        matrix c;cl(c.g);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)    
                for(int k=0;k<n;k++)
                c.g[i][j]+=g[i][k]*a.g[k][j];
                return c;
    }
}f[15];
pa fix(pa a){
    if(a.fi==0) return mk(0,1);
    if(a.se==0) return mk(1,0);
    int d=__gcd(a.fi,a.se);
    a.fi/=d,a.se/=d;
    if(a.fi<0) a.fi*=-1,a.se*=-1;
    return a;
}
void add(int p){
    map<pa ,vector<int>>cnt;
    for(int i=0;i<n;i++) if(i!=p){
        int dx=x[i]-x[p],dy=y[i]-y[p];
        cnt[fix(mk(dx,dy))].pb(i);
    }
    int sz=cnt.size();
    for(auto u:cnt){
        u.se.pb(p),flg=1;
        for(auto v:u.se){
            f[0].g[p][v]+=1.0/u.se.size()/sz;
            if(v<p) flg=0;
        }
        if(flg) lines.pb(u.se);
    }
}
int main(){
#ifdef Devil_Gary
    freopen("in.txt","r",stdin);
#endif
    n=read();
    for(int i=0;i<n;i++) x[i]=read(),y[i]=read();
    for(int i=0;i<n;i++) add(i);
    for(int i=1;i<=14;i++)  f[i]=f[i-1]*f[i-1];
    for(int Q=read();Q;Q--){
        int t=read()-1,m=read()-1;
        for(int i=0;i<n;i++) pro[i]=0;pro[t]=1.0; 
        for(int i=0;i<=14;i++){
            if(m&(1<<i)){
                for(int j=0;j<n;j++) tmp[j]=pro[j],pro[j]=0;
                for(int j=0;j<n;j++) for(int k=0;k<n;k++){
                    pro[j]+=tmp[k]*f[i].g[j][k]; 
                }
            }
        }
        ans=0;
        for(auto line:lines){
            double temp=0;
            for(auto u:line) temp+=pro[u];
            ans=max(ans,temp/line.size());
        }
        printf("%.12lf\n",ans);
    }
}

两个点

一个是马可夫链(状态矩阵)的反推

Codeforces 989E A Trance of Nightfall 矩阵快速幂+DP

Codeforces 989E A Trance of Nightfall 矩阵快速幂+DP

第二个点是怎么把在一条线上的点聚集起来(全是整点的情况下)

 

pa fix(pa a){
    if(a.fi==0) return mk(0,1);
    if(a.se==0) return mk(1,0);
    int d=__gcd(a.fi,a.se);
    a.fi/=d,a.se/=d;
    if(a.fi<0) a.fi*=-1,a.se*=-1;
    return a;
}
    for(int i=0;i<n;i++) if(i!=p){
        int dx=x[i]-x[p],dy=y[i]-y[p];
        cnt[fix(mk(dx,dy))].pb(i);
    }

这边用的是向量v = (dx, dy) 然后把v变成一个方向向量(除以dx dy的gcd),然后将一个方向的聚集在vector里