专栏文章

题解：CF1970E1 Trails (Easy)

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

文章操作

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

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

CF1970E1 Trails (Easy)

题意

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

数据范围

m≤100,n≤103m \le 100,n \le 10^3。

思路

令 tit_i 是小屋 ii 到湖边的路径数量和（也就是 si+lis_i+l_i）。
考虑 DP。
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)

代码

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 f[1010][110];
int t[110];
int s[110],l[110];
int ans;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>m>>n;//m,n是反的
    for(int i=1;i<=m;i++){
        cin>>s[i];
    }
    for(int i=1;i<=m;i++){
        cin>>l[i];
        t[i]=l[i]+s[i];
    }
    f[0][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int cnt=0;
            for(int k=1;k<=m;k++){
                cnt+=(t[j]*t[k]-l[j]*l[k])*f[i-1][k];
                cnt%=mod;
            }
            f[i][j]=cnt;
        }
    }
    for(int i=1;i<=m;i++){
        ans+=f[n][i];
        ans%=mod;
    }
    cout<<ans<<'\n';
    return 0;
}
提交记录

评论

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

正在加载评论...