专栏文章

题解：CF1970E2 Trails (Medium)

ssongge888
CF1970E2题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip1ep2c
此快照首次捕获于
2025/12/03 04:35
3 个月前
此快照最后确认于
2025/12/03 04:35
3 个月前
查看原文

CF1970E2 Trails (Medium)

题意

有 mm 个小屋，每个小屋通过若干条短路径和长路径与湖边的集合点相连。哈利每天从一个小屋出发，先走一条路径到湖边，再走一条路径到另一个小屋（可是同一个小屋），但这两条路径中至少有一条必须是短路径。已知哈利从小屋 11 出发，连续走 nn 天，问有多少种不同的路线，结果对 109+710^9+7 取模。

数据范围

m≤100,n≤109m \le 100,n \le 10^9。

思路

这个题对比简化版的区别就是 nn 的大小从 10310^3 到了 10910^9。
先想一下简化版的思路。
令 tit_i 是小屋 ii 到湖边的路径数量和（也就是 si+lis_i+l_i）。
fi,jf_{i,j} 表示第 ii 天到小屋 jj 的路线数，可以由 fi−1,kf_{i-1,k} 转移而来（1≤k≤m1 \le k \le m），所有的路径数为 tj×tkt_j \times t_k，但是不能全部是短路径，所以要减去 sj×sks_j \times s_k，则转移方程如下：
fi,j=∑k=1mfi−1,k×(tj×tk−sj×sk)f_{i,j}= \sum_{k=1}^{m} f_{i-1,k}\times(t_j \times t_k-s_j \times s_k)
发现系数 tj×tk−sj×skt_j \times t_k-s_j \times s_k 是不变的，考虑矩阵加速。
我们可以一个矩阵 AA：
Ai=[fi,1,fi,2,…,fi,m]A_i=[f_{i,1},f_{i,2},\dots,f_{i,m}]
另外有一个矩阵 BB，满足：
Ai+1=Ai×BA_{i+1}=A_i \times B
可以推出 BB：
B=[t1t1−l1l1t1t2−l1l2⋯t1tm−l1lmt2t1−l2l1t2t2−l2l2⋯t2tm−l2lm⋮⋮⋱⋮tmt1−lml1tmt2−lml2⋯tmtm−lmlm]B=\left[ \begin{array}{cccc} t_1 t_1 - l_1 l_1 & t_1 t_2 - l_1 l_2 & \cdots & t_1 t_m - l_1 l_m \\ t_2 t_1 - l_2 l_1 & t_2 t_2 - l_2 l_2 & \cdots & t_2 t_m - l_2 l_m \\ \vdots & \vdots & \ddots & \vdots \\ t_m t_1 - l_m l_1 & t_m t_2 - l_m l_2 & \cdots & t_m t_m - l_m l_m \\ \end{array} \right]
最后 An=A0×BnA_n=A_0 \times B^n，答案就是 ∑i=1mfn,i\sum_{i=1}^{m} f_{n,i}。

代码

CPP
//矩阵的两维和题解中是相反的
#include<bits/stdc++.h>
#define int long long
#define double long double
#define bug cout<<"___songge888___"<<'\n';
using namespace std;
const int MOD=1e9+7;
int n,m;
int s[105],l[105];
int t[105];

struct Matrix{
    int m[105][105],n;
    void init(int size){
        n=size;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                m[i][j]=(i==j);
            }
        }
    }
    Matrix operator*(const Matrix &b)const{
        Matrix res;
        res.n=n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                res.m[i][j]=0;
                for(int k=1;k<=n;k++){
                    res.m[i][j]+=m[i][k]*b.m[k][j];
                    res.m[i][j]%=MOD;
                }
            }
        }
        return res;
    }
};
Matrix matrix_qpow(Matrix base,int exp){
    Matrix res;
    res.init(base.n);
    while(exp>0){
        if(exp&1){
            res=res*base;
        }
        base=base*base;
        exp>>=1;
    }
    return res;
}
int ans;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        cin>>s[i];
    }
    for(int i=1;i<=m;i++){
        cin>>l[i];
        t[i]=s[i]+l[i];
    }
    Matrix A,B;
    A.n=B.n=m;
    B.m[1][1]=1;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            A.m[i][j]=t[i]*t[j]-l[i]*l[j];
            A.m[i][j]%=MOD;
        }
    }
    B=B*matrix_qpow(A,n);
    for(int i=1;i<=m;i++){
        ans+=B.m[1][i];
        ans%=MOD;
    }
    cout<<ans;
    return 0;
}
提交记录

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...