当前位置：首页 > news >正文

2024.8.23

news 来源：原创 2024/9/21 5:42:43

130124202408231008

DATE #:20240823

ITEM #:DOC

WEEK #:FRIDAY

DAIL #:捌月二十

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\%$ 的数据， $\le 4$ ， $\sum s \le 30$ 。

对于 $100\%$ 的数据， $\le T \le 15$ ， $\le n \le 100$ ， $\le \sum s \le 3141592$ 。

2021/5/14 加强 by SSerxhs&滑大稽

//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)&&deg[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

[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);
}