XCPC Notes

Appearance

发布时间：2024-09-29

求斐波那契数列 ​

(1110)⋅(fi−1fi−2)=(fifi−1) \left( \begin{matrix} 1 & 1\\ 1 & 0 \end{matrix} \right) \cdot \left( \begin{matrix} f_{i-1}\\ f_{i-2} \end{matrix} \right)= \left( \begin{matrix} f_{i}\\ f_{i-1} \end{matrix} \right)

模板 ​

cpp
struct Matrix{
    int a[N][N];
    Matrix(){
        memset(a,0,sizeof a);
    }
    Matrix operator * (const Matrix &b)const{
        Matrix res;
        for(int i=1;i<N;i++){
            for(int j=1;j<N;j++){
                for(int k=1;k<N;k++)(res.a[i][j]+=a[i][k]*b.a[k][j])%=mod;
            }
        }
        return res;
    }
};
Matrix qpow(Matrix a,int b){
    Matrix ans;
    for(int i=1;i<N;i++)ans.a[i][i]=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a;
        a=a*a;
    }
    return ans;
}
void solve(){
    int n,k;
    cin>>n>>k;
    Matrix a;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cin>>a.a[i][j];
    }
    a=qpow(a,k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cout<<a.a[i][j]<<" \n"[j==n];
    }
}

矩阵快速幂求解经过n条边的最短路 ​

  • 邻接矩阵AA,AnA^n表示经过nn条路径的最短路
cpp
struct Matrix{
    int m[210][210];
    int x,y;
    Matrix(int _x=0,int _y=0):x(_x),y(_y){memset(m,0x3f,sizeof m);}
    Matrix operator*(const Matrix &t)const{
        Matrix res(x,t.y);
        for(int k=1;k<=y;k++){
            for(int i=1;i<=x;i++){
                for(int j=1;j<=t.y;j++){
                    res.m[i][j]=min(res.m[i][j],m[i][k]+t.m[k][j]);
                }
            }
        }
        return res;
    };
};
Matrix qpow(Matrix a,int b){
    Matrix res(a.x,a.y);
    for(int i=1;i<=a.x;i++)res.m[i][i]=0;
    while(b){
        if(b&1)res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
void solve(){
    int n,t,s,e;
    cin>>n>>t>>s>>e;
    map<int,int> mp;
    auto get=[&](int x){
        if(mp.count(x))return mp[x];
        return mp[x]=mp.size()+1;
    };
    s=get(s),e=get(e);
    Matrix ans;
    for(int i=1;i<=t;i++){
        int u,v,w;
        cin>>w>>u>>v;
        u=get(u),v=get(v);
        ans.m[u][v]=ans.m[v][u]=min(ans.m[u][v],w);
    }
    ans.x=ans.y=mp.size();
    ans=qpow(ans,n);
    cout<<ans.m[s][e]<<"\n";
}

P6772 [NOI2020] 美食家 ​

题目描述 ​

坐落在 Bzeroth 大陆上的精灵王国击退地灾军团的入侵后，经过十余年的休养生息，重新成为了一片欣欣向荣的乐土，吸引着八方游客。小 W 是一位游历过世界各地的著名美食家，现在也慕名来到了精灵王国。

精灵王国共有 nn 座城市，城市从 11 到 nn 编号，其中城市 ii 的美食能为小 W 提供 cic_i 的愉悦值。精灵王国的城市通过 mm 条单向道路连接，道路从 11 到 mm 编号，其中道路 ii 的起点为城市 uiu_i ，终点为城市 viv_i，沿它通行需要花费 wiw_i 天。也就是说，若小 W 在第 dd 天从城市 uiu_i 沿道路 ii 通行，那么他会在第 d+wid + w_i 天到达城市 viv_i。

小 W 计划在精灵王国进行一场为期 TT 天的旅行，更具体地：他会在第 00 天从城市 11 出发，经过 TT 天的旅行，最终在恰好第 TT 天回到城市 11 结束旅行。由于小 W 是一位美食家，每当他到达一座城市时（包括第 00 天和第 TT 天的城市 11），他都会品尝该城市的美食并获得其所提供的愉悦值，若小 W 多次到达同一座城市，他将获得多次愉悦值。注意旅行途中小 W 不能在任何城市停留，即当他到达一座城市且还未结束旅行时，他当天必须立即从该城市出发前往其他城市。

对于上图，小 W 一种为期 1111 天的可行旅游方案为 1→2→1→2→3→11 \to 2 \to 1 \to 2 \to 3 \to 1：

  • 第 00 天，小 W 从城市 11 开始旅行，获得愉悦值 11 并向城市 22 出发。
  • 第 11 天，小 W 到达城市 22，获得愉悦值 33 并向城市 11 出发。
  • 第 44 天，小 W 到达城市 11，获得愉悦值 11 并向城市 22 出发。
  • 第 55 天，小 W 到达城市 22，获得愉悦值 33 并向城市 33 出发。
  • 第 77 天，小 W 到达城市 33，获得愉悦值 44 并向城市 11 出发。
  • 第 1111 天，小 W 到达城市 11，获得愉悦值 11 并结束旅行。
  • 小 W 在该旅行中获得的愉悦值之和为 1313。

此外，精灵王国会在不同的时间举办 kk 次美食节。具体来说，第 ii 次美食节将于第 tit_i 天在城市 xix_i 举办，若小 W 第 tit_i 天时恰好在城市 xix_i，那么他在品尝城市 xix_i 的美食时会额外得到 yiy_i 的愉悦值。现在小 W 想请作为精灵王国接待使者的你帮他算出，他在旅行中能获得的愉悦值之和的最大值。

对于所有测试点：

1≤n≤501 \leq n \leq 50，n≤m≤501n \leq m \leq 501，0≤k≤2000 \leq k \leq 200，1≤ti≤T≤1091 \leq t_i \leq T \leq 10^9。

1≤wi≤51 \leq w_i \leq 5，1≤ci≤525011 \leq c_i \leq 52501，1≤ui,vi,xi≤n1 \leq u_i, v_i, x_i \leq n，1≤yi≤1091 \leq y_i \leq 10^9。

思路：

  • TT很大，需要使用矩阵快速幂，但是矩阵快速幂需要满足边权为11
  • 因为边权最多为55,考虑拆点，对于(u,v,w)(u,v,w)变成((u,w),(v,1),cv)((u,w),(v,1),c_v)连边
  • 那么如果没有kk个派对，那么答案怎么算
  • 初始有一个1*5n的矩阵ans1,ians_{1,i}代表到达ii的价值
  • 那么还有一个5n*5n的矩阵AA,Ai,jA_{i,j}代表ii到jj的最大价值
  • 答案就是[ans⋅AT]1,1[ans \cdot A^T]_{1,1}
  • 如果有派队，那么根据时间走，到达对应的时间，ansans对应的点加上贡献
  • 复杂度O(kn3log⁡T)O(kn^3 \log T)，会超时
  • 考虑对AA二进制分组预处理，复杂度为O(n3log⁡T)O(n^3 \log T)
  • 那么每次询问时，一次矩阵乘法是1*5n和5n*5n的矩阵相乘，复杂度为O(kn2log⁡T)O(kn^2 \log T)，可以通过
cpp
struct Matrix{
    vector<vector<int>> m;
    int x,y;
    Matrix(int _x=0,int _y=0):x(_x),y(_y){m.assign(_x+1,vector<int>(_y+1,-INF));}
    Matrix operator*(const Matrix &t)const{
        Matrix res(x,t.y);
        for(int k=1;k<=y;k++){
            for(int i=1;i<=x;i++){
                for(int j=1;j<=t.y;j++){
                    res.m[i][j]=max(res.m[i][j],m[i][k]+t.m[k][j]);
                }
            }
        }
        return res;
    };
    void print(){
        for(int i=1;i<=x;i++){
            for(int j=1;j<=y;j++){
                cout<<m[i][j]<<" ";
            }
            cout<<"\n";
        }
    }
};
Matrix qpow(Matrix a,int b){
    Matrix res=a;
    b--;
    while(b){
        if(b&1)res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
int getid(int x,int y){
    return (x-1)*5+y;
}
void solve(){
    int n,m,T,k;
    cin>>n>>m>>T>>k;
    vector<Matrix> mat(32);
    mat[0]=Matrix(5*n,5*n);
    vector<int> c(n+1);
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<5;j++)mat[0].m[getid(i,j)][getid(i,j+1)]=0;
    }
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        mat[0].m[getid(u,w)][getid(v,1)]=max(mat[0].m[getid(u,w)][getid(v,1)],c[v]);
    }
    vector<array<int,3>> dot(k);
    for(auto &[t,x,y]:dot)cin>>t>>x>>y;
    ranges::sort(dot);
    Matrix ans(1,5*n);
    ans.m[1][getid(1,1)]=c[1];
    for(int i=1;i<32;i++)mat[i]=mat[i-1]*mat[i-1];
    int lst=0;
    for(auto &[t,x,y]:dot){
        int r=t-lst;
        for(int i=0;i<32;i++){
            if(r>>i&1)ans=ans*mat[i];
        }
        ans.m[1][getid(x,1)]+=y;
        lst=t;
    }
    if(lst<T){
        int r=T-lst;
        for(int i=0;i<32;i++){
            if(r>>i&1)ans=ans*mat[i];
        }
    }
    cout<<(ans.m[1][getid(1,1)]<0?-1:ans.m[1][getid(1,1)])<<"\n";
}

CF576D Flights for Regular Customers ​

一张有向图，nn个点mm条边，从11走到nn

只有走过did_i条边，才能走第ii条

问最少要走多少条边，或者无法到达

1≤n,m≤150,di≤1091 \leq n,m \leq 150,d_i \leq 10^9

思路：

  • 定义一个矩阵AA,A1,iA_{1,i}表示可以从11到ii
  • GG是一个邻接矩阵
  • 对did_i排序
  • 那么可以用GG更新在走ii条边前的AA
  • 然后对可达点跑全源bfs，更新答案为T+disnT+dis_n
  • 复杂度：O(m(n3log⁡d+n2))O(m(n^3\log d+n^2))，超时
  • 考虑矩阵只有01，公式可以bitset优化
  • 复杂度为：O(m(n3log⁡dω+n2))O(m(\frac{n^3\log d}{\omega}+n^2))
cpp
struct Matrix{
    vector<bitset<151>> m;
    int x,y;
    Matrix(int _x=0,int _y=0):x(_x),y(_y){m.assign(_x+1,bitset<151>());}
    Matrix operator*(const Matrix &t)const{
        Matrix res(x,t.y);
        for(int k=1;k<=y;k++){
            for(int i=1;i<=x;i++){
                if(m[i][k])res.m[i]|=t.m[k];
            }
        }
        return res;
    };
};
Matrix qpow(Matrix a,int b){
    Matrix res(a.x,a.y);
    for(int i=1;i<=a.x;i++){
        res.m[i][i]=1;
    }
    while(b){
        if(b&1)res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
void solve(){
    int n,m;
    cin>>n>>m;
    Matrix A(1,n),G(n,n);
    A.m[1][1]=1;
    vector<array<int,3>> e(m);
    vector<int> dis(n+1);
    for(auto &[d,u,v]:e)cin>>u>>v>>d;
    ranges::sort(e);
    int T=0;
    auto bfs=[&](){
        fill(dis.begin(),dis.end(),INF);
        queue<int> q;
        for(int i=1;i<=n;i++){
            if(A.m[1][i])q.push(i),dis[i]=0;
        }
        while(!q.empty()){
            auto u=q.front();
            q.pop();
            for(int i=1;i<=n;i++){
                if(G.m[u][i]&&dis[i]==INF){
                    dis[i]=dis[u]+1;
                    q.push(i);
                }
            }
        }
    };
    int ans=INF;
    for(int i=0;i<m;i++){
        auto [d,u,v]=e[i];
        int r=d-T;
        A=A*qpow(G,r);
        G.m[u][v]=1;
        if(i==m-1||T!=d){
            bfs();
            ans=min(ans,dis[n]+d);
        }
        T=d;
    }
    if(ans==INF)cout<<"Impossible\n";
    else cout<<ans<<"\n";
}

Wenwei Lin · 2022 — 2025