「UR #15」奥林匹克环城马拉松

「UR #15」奥林匹克环城马拉松

八月 31, 2020 · OI 题解

给定一张 $n$ 个点的树或基环树，树上的每条边 $(u_i, v_i, w_i)$ 代表 $(u_i, v_i)$ 间有 $w_i$ 道路相连。

你需要统计有多少种从任意点出发的本质不同路径，使得经过所有道路恰好一次。

路径可以认为是一个从某个点出发，由经过道路编号和方向组成的序列。两条路线被认为是相同的当且仅当两序列相同，或更换起始边后两序列相同。

$n, w_i \leq 1000$。

题解

BEST 定理的简单应用。

我们可以把这个问题转化为两部分：

  1. 为无向边定向
  2. 套用 BEST 定理计算（生成树形图计数）

前一部分我们可以从树的情况推广。如果 $m=n-1$，那么显然两点之间的无向边，转化成有向边刚好一半一半。对于基环树的情况，我们枚举走整个环的次数，那么也可以计算出有向边。

后一部分，我们考虑基环树可以枚举一条断边，然后就是把所有指向根的重边条数一次乘起来（选任意一条作为外向树的一部分）。实现中需要处理前缀和保证复杂度。

坑

  1. 对于我的实现，需要保证环一路过去的端点依次按照经过顺序排序。也就是存无向边的数组可能需要把 $(u,v,w)$ swap 成 $(v,u,w)$。不过我倒是写的时候就注意到了。
  2. 这题预处理阶乘的范围有坑啊有坑（x

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
const int N=1e3+10,mod=998244353,L=1e4+10;
int n,m,ans,tot,top,min=INT_MAX,cir[N],w0[N],w1[N],deg[N],u[N],v[N],w[N],pre[N],suf[N],stk[N],hed[N],to[N<<1],val[N<<1],nxt[N<<1],fac[N*L],ifac[L];
bool vis[N],onc[N],inc[N];
void initgraph(){
  tot=0;
  memset(hed,-1,sizeof(hed));
}
void initfac(){
  fac[0]=ifac[0]=ifac[1]=1;
  for(int i=1;i<N*L;i++)fac[i]=(long long)fac[i-1]*i%mod;
  for(int i=2;i<L;i++)ifac[i]=(long long)(mod-mod/i)*ifac[mod%i]%mod;
  for(int i=1;i<L;i++)ifac[i]=(long long)ifac[i-1]*ifac[i]%mod;
}
inline int C(int n,int m){return n<m?0:(long long)fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
inline void link(int u,int v,int w){nxt[tot]=hed[u],to[tot]=v,val[tot]=w,hed[u]=tot++;}
inline int calc_fac(int x){
  int res=1;
  for(int i=1;i<=x;i++)res=(long long)res*i%mod;
  return res;
}
void solve_tree(){
  int ans=1;
  for(int u,v,w,i=1;i<=m;i++){
    scanf("%d%d%d",&u,&v,&w);
    if(w&1){puts("0"); return;}
    deg[u]+=w>>1,deg[v]+=w>>1;
    ans=(long long)ans*C(w,w>>1)%mod*(w>>1)%mod;
  }
  for(int i=1;i<=n;i++)ans=(long long)ans*fac[deg[i]-1]%mod;
  printf("%d\n",ans);
}
void dfs(int u,int fa){
  stk[++top]=u,vis[u]=1;
  // printf("dfs %d %d\n",u,fa);
  for(int i=hed[u];~i;i=nxt[i])
    if(to[i]!=fa){
      // printf("%d -> %d\n",u,to[i]);
      if(vis[to[i]]){
        if(*cir)continue;
        cir[++*cir]=val[i];
        // printf("%d : %d\n",i,val[i]);
        for(int x=u;x!=to[i];x=to[pre[x]^1]){
          cir[++*cir]=val[pre[x]];
          // printf("(%d) %d : %d\n",x,pre[x],val[pre[x]]);
        }
      }else{
        pre[to[i]]=i;
        dfs(to[i],u);
      }
    }
  --top;
}
void ordered_circle(){
  int same=-1;
  if(u[cir[1]]==u[cir[2]])same=u[cir[1]];
  if(u[cir[1]]==v[cir[2]])same=u[cir[1]];
  if(v[cir[1]]==u[cir[2]])same=v[cir[1]];
  if(v[cir[1]]==v[cir[2]])same=v[cir[1]];
  assert(~same);
  int s=u[cir[1]]+v[cir[1]]-same;
  for(int i=1;i<=*cir;i++){
    // printf("i=%d cir=%d s=%d : u=%d v=%d\n",i,cir[i],s,u[cir[i]],v[cir[i]]);
    if(u[cir[i]]!=s)std::swap(u[cir[i]],v[cir[i]]);
    s=v[cir[i]];
  }
}
int calc(int cur){
  memset(deg,0,sizeof(deg));
  int ans=1,sum=0,ano=1;
  for(int i=1;i<=m;i++){
    if(inc[i]){
      if((w[i]+cur)&1)return 0;
      w0[i]=(w[i]+cur)>>1;
      w1[i]=(w[i]-cur)>>1;
    }else{
      w0[i]=w1[i]=w[i]>>1;
    }
    deg[u[i]]+=w1[i];
    deg[v[i]]+=w0[i];
    ans=(long long)ans*C(w[i],w0[i])%mod;
  }
  for(int i=1;i<=n;i++)ans=(long long)ans*fac[deg[i]-1]%mod;
  for(int i=1;i<=m;i++)if(!inc[i])ano=(long long)ano*w0[i]%mod;
  for(int k=1;k<=*cir;k++)pre[k]=(long long)pre[k-1]*w0[cir[k]]%mod;
  for(int k=*cir;k>=1;k--)suf[k]=(long long)suf[k+1]*w1[cir[k]]%mod;
  for(int k=1;k<=*cir;k++){
    sum=(sum+(long long)pre[k-1]*suf[k+1]%mod*ano)%mod;
  }
  return (long long)sum*ans%mod;
}
int main(){
#ifdef Ciel
  freopen("1.in","r",stdin);
  // freopen("comp/data.in","r",stdin);
#endif
  initfac();
  initgraph();
  scanf("%d%d",&n,&m);
  if(n==m+1)return solve_tree(),0;
  for(int i=1;i<=m;i++){
    scanf("%d%d%d",&u[i],&v[i],&w[i]);
    link(u[i],v[i],i);
    link(v[i],u[i],i);
    deg[u[i]]+=w[i];
    deg[v[i]]+=w[i];
  }
  for(int i=1;i<=n;i++)if(deg[i]&1)return puts("0"),0;
  dfs(1,0);
  ordered_circle();
  for(int i=1;i<=*cir;i++){
    inc[cir[i]]=onc[u[cir[i]]]=onc[v[cir[i]]]=true;
    min=std::min(min,w[cir[i]]);
  }
  // for(int i=1;i<=m;i++)printf("%d %d %d %d\n",u[i],v[i],w[i],inc[i]);
  pre[0]=suf[0]=pre[*cir+1]=suf[*cir+1]=1;
  for(int d=-min;d<=min;d++)ans=(ans+calc(d))%mod;
  printf("%d\n",ans);
}