DATE #:20240823
ITEM #:DOC
WEEK #:FRIDAY
DAIL #:捌月二十
TAGS
<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=2602523834&auto=0&height=66" width="330"></iframe> < BGM = "Forest Mixtape（Tsuki)" > < theme = oi-graph theory Eulerian > < [NULL] > < [空] > < [空] >冰岛的温柔是克莱因蓝再加点莫奈的灰。
BEST定理
BEST定理是用于处理欧拉回路计数问题的
我们首先做如下定义：
\(t_x\)为以x为根的树数量，可以使用矩阵树定理求解
\(deg_i\)为i的度
对于一个有向欧拉图，它的欧拉回路数量是：
\[t_sdeg_s!\prod_{i\in V}(deg_i-1)![i\ne s]=t_x\prod_{i\in V}(deg_i-1)! \]证明
我们发现，对于一个欧拉图而言，从每个点出发是一样的，所以考虑以1为起点
计算以1为根的生成树数量，将点i删去，在考虑生成树就是以该节点为根的生成树数量
生成树使用矩阵树定理求出
对于一棵树，我们这里激进一点，就让他是一棵根向树
对每一条边，我们给定一个顺序，指向根的顺序最靠后
那么顺序的方案数就是\(deg_s!\prod(dge_u-1)![u\ne s]\)
再乘上以1为根的生成树数量就是原式了
那么我们只要证明每种标号方案都对应这一种欧拉回路就可以了
在每次经过一条边后，我们删去它
剩下的边一定要满足如下条件才是欧拉图
-
图弱联通
-
只有两个节点出度和入度相差一，其他节点正常
（正常欧拉图所有节点入度等于出度
若删去的边 \((u,v)\) 是非树边，由于树边是每个点最后离开的边 \((u,v)\) 之间的树边一定还没有被删去，则 \(u\) 到 \(v\) 之间可以直接通过树边形成弱连通；
若删去的边是树边，则删去后 \(u\) 与剩下的图完全断开，相当于删去了一条链末端的一条边，剩余边仍然弱连通。
所以删掉一条边后剩下的图仍然有欧拉路径.
每个边所在的顺序都是合法且不重复的欧拉路径
P5807 【模板】BEST 定理 | Which Dreamed It
【模板】BEST 定理 | Which Dreamed It
题目描述
有 \(n\) 个房间，每个房间有若干把钥匙能够打开特定房间的门。
最初你在房间 \(1\)。每当你到达一个房间，你可以选择该房间的一把钥匙，前往该钥匙对应的房间，并将该钥匙丢到垃圾桶中。
你希望最终回到房间 \(1\)，且垃圾桶中有所有的钥匙。
你需要求出方案数，答案对 \(10^6 + 3\) 取模。两组方案不同，当且仅当使用钥匙的顺序不同。
注意，每把钥匙都是不同的。
原 BZOJ3659。
输入格式
本题有多组数据。
第一行一个整数 \(T\)，表示数据组数。
对于每组数据：
第一行一个整数 \(n\)。
接下来 \(n\) 行，第 \(i\) 行描述房间 \(i\)：
首先一个数 \(s\)，表示这个房间的钥匙数目，接下来 \(s\) 个数，分别描述每把钥匙能够打开的房间的门。
输出格式
对于每组数据，一行一个整数，表示答案对 \(10^6+3\) 取模后的值。
样例 #1
样例输入 #1
2 1 0 2 1 1 1 2样例输出 #1
1 0提示
【样例说明】
在第一组样例中，没有钥匙，则方案数为 \(1\)。
在第二组样例中，你不可能使用第二个房间的钥匙，所以方案数为 \(0\)。
【数据范围】
对于 \(50\%\) 的数据，\(n \le 4\)，\(\sum s \le 30\)。
对于 \(100\%\) 的数据，\(1 \le T \le 15\)，\(1 \le n \le 100\)，\(0 \le \sum s \le 3141592\)。
//2024.8.23
//by white_ice
//【模板】BESt 定理 | Which kdreamed kit | mod5807
//model
#include<bits/stdc++.h>
//#include"need.cpp"
using namespace std;
#define itn long long
#define int long long
constexpr int oo = 110;
constexpr int op = 500010;
constexpr int mod = 1000003;
int t;int n;
int ki[op];int fa[op];
itn res;itn fac[op];itn deg[op];
itn kd[oo][oo];itn kk[oo][oo];itn ka[oo][oo];
__inline itn Gauss(){
itn ans = 1;
for (int i=1;i<n;i++){
for (int j=i+1;j<n;j++){
while(kk[j][i]){
itn t = kk[i][i]/kk[j][i];
for(int k=i;k<n;k++)
kk[i][k] = (kk[i][k]-t*kk[j][k])%mod;
swap(kk[i], kk[j]),ans=(-ans%mod+mod)%mod;
}
}
if (kk[i][i]) (ans *= kk[i][i])%=mod;
}
return (ans % mod + mod) % mod;
}
__inline void clear(){
memset(kk,0,sizeof(kk));
memset(ka,0,sizeof(ka));
memset(kd,0,sizeof(kd));
memset(ki,0,sizeof(ki));
for (int i=1;i<=n;i++)fa[i] = i;
}
__inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
main(void){
//fre();
cin.tie(0)->sync_with_stdio(0);
cin >> t;fac[0] = 1;
for (itn i=1;i<=500000;i++)
fac[i] = fac[i-1]*i%mod;
while (t --){
cin >> n;clear();
for (int i=1;i<=n;i++){
int k, s;cin >> s;deg[i] = s;
for (int j=1;j<=s;j++){
cin >> k;ka[i][k]++,kd[k][k]++,ki[k]++;
if (find(i) != find(k))
fa[find(i)]=find(k);
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;++j)
kk[i][j] = ((kd[i][j]-ka[i][j])%mod+mod)%mod;
for (int i=1;i<=n;i++)
if (ki[i] != deg[i]) goto x1;
for (int i=1;i<=n;i++)
if (find(i)!=find(1)&°[i]) goto x1;
res = deg[1]*Gauss()%mod;
for (int i = 1;i <= n;i++)
if (deg[i]) (res *= fac[deg[i]-1])%=mod;
for (int i = 2;i <= n;i++)
if (find(i) == find(1)) goto x2;
cout << fac[deg[1]] << '\n';continue;
x1: puts("0");continue;
x2: cout << res << '\n';
}
exit(0);
}
[AGC051D] C4
题面翻译
有一张 \(4\) 个点 \(4\) 条边的简单无向连通图，点的编号分别为 \(1,2,3,4\) ，边分别连接着 $e1:(1,2),e2:(2,3),e3:(3,4),e4:(4,1) $。
给定 \(4\) 个数 \(v_1,v_2,v_3,v_4\) 求满足以下条件的路径数量：
从 \(1\) 号点出发并到 \(1\) 号点结束，且经过第 \(i\) 条边 \(e_i\) 恰好 \(v_i\) 次。
你需要输出路径数对 \(998244353\) 取模的结果。
\(v_1,v_2,v_3,v_4 \le 5 \times 10^5\)
题目描述
以下の無向グラフにおいて、$ S $ から $ S $ へのウォークであって辺 $ ST $, $ TU $, $ UV $, $ VS $ をそれぞれ $ a $, $ b $, $ c $, $ d $ 回通るもの (向きは不問) の数を $ 998,244,353 $ で割った余りを求めてください。
输入格式
入力は標準入力から以下の形式で与えられる。
$ a $ $ b $ $ c $ $ d $
输出格式
答えを出力せよ。
样例 #1
样例输入 #1
2 2 2 2样例输出 #1
10样例 #2
样例输入 #2
1 2 3 4样例输出 #2
0样例 #3
样例输入 #3
470000 480000 490000 500000样例输出 #3
712808431提示
注記
$ S $ から $ S $ へのウォークとは、頂点の列 $ v_0\ =\ S,\ v_1,\ \ldots,\ v_k\ =\ S $ であって、各 $ i\ (0\ \leq\ i\ <\ k) $ について $ v_i $ と $ v_{i+1} $ を結ぶ辺があるものをいいます。 $ 2 $ つのウォークは、列として異なるときに異なるとみなされます。
制約
- $ 1\ \leq\ a,\ b,\ c,\ d\ \leq\ 500,000 $
- 入力中の全ての値は整数である。
Sample Explanation 1
条件を満たすウォークは $ 10 $ 個あり、その一例は $ S $ $ \rightarrow $ $ T $ $ \rightarrow $ $ U $ $ \rightarrow $ $ V $ $ \rightarrow $ $ U $ $ \rightarrow $ $ T $ $ \rightarrow $ $ S $ $ \rightarrow $ $ V $ $ \rightarrow $ $ S $ です。
//2024.8.23
//by white_ice
//[AGC051D] C4 | AT_agc051_d
//BEST定理
#include<bits/stdc++.h>
//#include"need.cpp"
using namespace std;
#define itn long long
#define int long long
constexpr int mod = 998244353;
constexpr int oo = 1000006;
int fac[oo],ifac[oo];itn a,b,c,d;
void init(){
fac[0]=fac[1]=ifac[1]=ifac[0]=1;
for(int i=2;i<=600000;++i)ifac[i]=(mod-mod/i)*ifac[mod%i]%mod;
for(int i=2;i<=600000;++i)fac[i]=fac[i-1]*i%mod,ifac[i]=ifac[i]*ifac[i-1]%mod;
}
int check(){
if((a&1)!=(b&1))return 1;
if((b&1)!=(c&1))return 1;
if((c&1)!=(d&1))return 1;
return 0;
}
int check2(int i,int j,int k){
if(i<0||i>b)return 1;
if(j<0||j>c)return 1;
if(k<0||k>d)return 1;
return 0;
}
__inline int get(int st,int tu,int uv,int vs){int sv=d-vs,ut=b-tu,vu=c-uv;
return (st*tu*uv%mod+sv*st*tu%mod+sv*vu*ut%mod+sv*vu*st%mod)%mod;}
main(void){
//fre();
cin.tie(0)->sync_with_stdio(0);
cin >> a >> b >> c >> d;
init();
if(check()){cout<<0;return 0;}
int out=0;
for(int xa=0;xa<=a;++xa){
int xb=xa+(b-a)/2,xc=xb+(c-b)/2,xd=xc+(d-c)/2;
if(check2(xb,xc,xd))continue;
int tmps=d+xa-xd;itn tmpt=a+xb-xa;
itn tmpu=b+xc-xb;itn tmpv=c+xd-xc;
int tmp=(fac[tmps-1]*fac[tmpt-1]%mod)*(fac[tmpu-1]*fac[tmpv-1]%mod)%mod;
int itmp1=(ifac[xa]*ifac[a-xa]%mod)*(ifac[xb]*ifac[b-xb]%mod)%mod;
int itmp2=(ifac[xc]*ifac[c-xc]%mod)*(ifac[xd]*ifac[d-xd]%mod)%mod;
int itmp=itmp1*itmp2%mod;
out=(out+get(xa,xb,xc,xd)*tmps%mod*tmp%mod*itmp%mod)%mod;
}
cout << out << flush;
exit (0);
}
首先想到可以拆边，将一条边，拆成很多条，
题目就可以转化，即：求从S出发的欧拉路数
显然应当使用BEST定理求解，但是BEST有局限性：要求图有向
所以我们要将无向图转化为有向图处理
对于任意一组边，比如\(S \longleftrightarrow T\)，共有a条，
我们考虑将其拆成\(x_a\)条\(S \rightarrow T\)和\(a-x_a\)条\(T\rightarrow S\)的边
因为是欧拉回路的缘故，所以我们的拆分并不那么自由要有一定的限制
欧拉回路中，每个节点出度等于入度
所以。。。。
\[x_a+b-x_b = a-x_a+x_b \Rightarrow\\ x_b = x_a+\frac{b-a}{2} \]同理，另外的\(x_c,x_d\)也可以这么推出
所以欧拉图数量\(ec(V)\)就可以求出来了
但是对于这道题，还要加上一些东西：
- 题目中要求了起点，所以要乘上S的出度\(deg_s\)
- BEST定理中每条边都不同，但是在此题中，重边相同，所以答案要除以\(\prod_{e\in \{a,b,c,d\}}x_e!(e-x_e)!\)
答案就是：
\[\frac{ec(V)\times deg_s}{\prod_{e\in \{a,b,c,d\}}x_e!(e-x_e)!} \] 标签：itn,oo,23,2024.8,样例,int,欧拉,rightarrow From： https://www.cnblogs.com/white-ice/p/18377162