CF1970E2 Trails (Medium) 题解

FFTotoro · 2024-05-05 20:47:35 · 题解

点这里前往游记。

考虑 E1 做法，此时 n,m 很小，所以考虑如下简单 DP。因为一天至少要走一条短的小路，令 f_{i,j} 表示在第 i 天时的终点为 j 的方案数，则有：

边界条件 f_{0,1}=1。

考虑 E2 做法，此时 n\le 10^9，m 仍然 \le 10^3。发现对于每一对 (j,k)，转移时乘上的系数都是一定的，为 s_js_k+s_jl_k+s_kl_j。这是个矩阵乘法的形式，于是考虑建出转移矩阵 A 满足 a_{i,j}=s_is_j+s_il_j+s_jl_i，使用矩阵快速幂处理出 A^n。根据上面 DP 的边界条件，初始时有一个序列（向量）V=\{1,0,0,\ldots,0,0\}，令 R=V\times A^n，则答案为 \sum R_i。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int> > matrix;
const int p=1e9+7;
inline void add(int &x,int y){
  if((x+=y)>=p)x-=p;
} // 模意义下的加法，比 (x+=y)%=p 快很多
matrix operator *(matrix &a,matrix &b){
  matrix c(a.size(),vector<int>(b[0].size()));
  for(int i=0;i<a[0].size();i++)
    for(int j=0;j<a.size();j++)
      for(int k=0;k<b[0].size();k++)
        add(c[j][k],a[j][i]*b[i][k]%p);
  return c;
} // 矩阵乘法
main(){
  ios::sync_with_stdio(false);
  int m,n,c=0; cin>>m>>n;
  vector<int> s(m),l(m);
  for(auto &i:s)cin>>i;
  for(auto &i:l)cin>>i;
  matrix a(m,vector<int>(m)),b=a,w(1,vector<int>(m));
  for(int i=0;i<m;i++)
    for(int j=0;j<m;j++)
      b[i][j]=(i==j),a[i][j]=((s[i]+l[i])*s[j]%p+s[i]*l[j]%p)%p;
  w[0][0]=1;
  while(n){
    if(n&1)b=b*a;
    a=a*a,n>>=1;
  } // 进行矩阵快速幂
  w=w*b;
  for(auto i:w)for(int j:i)add(c,j); // 统计答案
  cout<<c<<endl;
  return 0;
}