【FJWC2019】子圖（容斥）（計數）（三元環 / 四元環計數）

題意： n ≤ 1 e 5 n\le 1e5 n≤1e5 個點， m ≤ 2 e 5 m\le 2e5 m≤2e5 條邊，求包含 k ≤ 4 k\le 4 k≤4 條邊的聯通塊個數

這裡有圖

k = 1 k=1 k=1，顯然為 m m m

k = 2 k=2 k=2，枚舉中間點組合數算即可

k = 3 k=3 k=3，有三種情況，一種是三元環，一種是鍊，一種是菊花圖

鍊：枚舉中間邊，算兩邊的貢獻，但兩邊的出點重合會退化為三元環

每個三元環會算三次，菊花圖枚舉根算，然後三元計數把多的減掉

k = 4 k=4 k=4

發現共 5 種情況

第 3 個組合數算

第 4 個可以求出每個點所在的三元環個數然後枚舉點算貢獻

第 2 個可以枚舉邊 2 , 3 2,3 2,3，然後算 2 和 3 出去 1 個或 2 個的貢獻，

當 1,4 或者 1,5 重合的時候回退化為 4，多算了兩邊需要減掉

第 1 個可以枚舉 3，然後按順序枚舉 3 的出邊，考慮目前邊與之前的拼接

但退化有點煩

當 1 和 4 重合 或者是 2 和 5 重合會被多算，在圖 4 中會在 3,4 被多算兩次

當 1 5 重合會退化成 5，多算了 4 次

當 1 4 并且 2 5 重合會被算到三元環裡面，多算 3 次

現在問題就是如何求四元環個數

依然按照三元環那樣排序，我們定義 4 元環“權值”最大為根

需要保證一個四元環隻會在最大的根算一次

枚舉根以及出邊，然後枚舉出邊的出點，對每個到根路徑為 2 的點維護條數，加上之前的條數過後将條數加 1，然後再倒過來加一遍就可以把每一個點的貢獻算上

代碼奉上：

static int ct[N], sm[N];
	for(int i=1; i<=n; i++){
		for(int j=0; j<v[i].size(); j++)
		if(cmp(i,v[i][j])){
			for(int e=0,t=v[i][j]; e<v[t].size(); e++)
			if(cmp(i,v[t][e])){
				int w = v[t][e];
				sm[i]+=ct[w]; sm[t]+=ct[w]; sm[w]+=ct[w]; ++ct[w];
			}
		}
		for(int j=0; j<v[i].size(); j++)
		if(cmp(i,v[i][j])){
			for(int e=0,t=v[i][j]; e<v[t].size(); e++)
			if(cmp(i,v[t][e])){
				int w = v[t][e]; sm[t] += --ct[w];
			}
		}
	} int ans = 0;
	for(int i = 1; i <= n; i++) Add(ans, sm[i]);
	return mul(ans, inv4);
           

#include<bits/stdc++.h>
#define cs const
using namespace std;
int read(){
	int cnt = 0, f = 1; char ch = 0;
	while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; }
	while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();
	return cnt * f;
}
cs int N = 1e5 + 5, M = 2e5 + 5;
cs int Mod = 1e9 + 7;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b;}
int mul(int a, int b){ return 1ll * a * b % Mod; }
void Add(int &a, int b){ a = add(a, b); }
cs int inv2 = (Mod+1)>>1, inv3 = (Mod+1)/3, inv6 = mul(inv2,inv3);
cs int inv4 = mul(inv2, inv2), inv24 = mul(inv4,inv6);
int n, m, k, x[M], y[M];
vector<int> v[N], A[N];
int C2(int x){ return mul(inv2, mul(x,x-1)); }
int C3(int x){ return mul(mul(inv6, x), mul(x-1, x-2)); }
int C4(int x){ return mul(mul(inv24, mul(x,x-1)), mul(x-2,x-3));}
namespace Subtask2{
	void Solve(){
		int ans = 0;
		for(int i=1; i<=n; i++) Add(ans, C2(v[i].size()));
		cout << ans;
	}
}
bool cmp(int x, int y){ return v[x].size() > v[y].size() || (v[x].size() == v[y].size() && x > y); }
int cir[N];
int Circle3(){
	int ans = 0;
	for(int i=1; i<=m; i++){
		if(cmp(x[i], y[i])) A[x[i]].push_back(y[i]);
		else A[y[i]].push_back(x[i]);
	}
	static int vis[N]; int TIME = 0;
	memset(vis, 0, sizeof(vis));
	memset(cir, 0, sizeof(cir));
	for(int i=1; i<=n; i++){
		++TIME;
		for(int j=0; j<A[i].size(); j++) vis[A[i][j]] = TIME;
		for(int j=0; j<A[i].size(); j++)
		for(int e=0,v=A[i][j]; e<A[v].size(); e++)
		if(vis[A[v][e]] == TIME) ++ans, ++cir[i], ++cir[v], ++cir[A[v][e]];
	} return ans;
}
namespace Subtask3{
	void Solve(){
		int ans = 0;
		for(int i=1; i<=n; i++) Add(ans, C3(v[i].size()));
		for(int i=1; i<=m; i++) Add(ans, mul(v[x[i]].size()-1, v[y[i]].size()-1));
		Add(ans, Mod-mul(2,Circle3())); cout << ans;
	}
}
int Circle4(){
	static int ct[N], sm[N];
	for(int i=1; i<=n; i++){
		for(int j=0; j<v[i].size(); j++)
		if(cmp(i,v[i][j])){
			for(int e=0,t=v[i][j]; e<v[t].size(); e++)
			if(cmp(i,v[t][e])){
				int w = v[t][e];
				sm[i]+=ct[w]; sm[t]+=ct[w]; sm[w]+=ct[w]; ++ct[w];
			}
		}
		for(int j=0; j<v[i].size(); j++)
		if(cmp(i,v[i][j])){
			for(int e=0,t=v[i][j]; e<v[t].size(); e++)
			if(cmp(i,v[t][e])){
				int w = v[t][e]; sm[t] += --ct[w];
			}
		}
	} int ans = 0;
	for(int i = 1; i <= n; i++) Add(ans, sm[i]);
	return mul(ans, inv4);
}
namespace Subtask4{
	int calc(){
		int ans = 0;
		for(int i=1; i<=n; i++) Add(ans, mul(cir[i], (int)v[i].size()-2));
		return ans;
	}
	void Solve(){
		int ans = 0;
		Add(ans, Mod-mul(3,Circle3()));
		for(int i=1; i<=n; i++) Add(ans, C4(v[i].size()));
		for(int i=1; i<=m; i++) 
		Add(ans, mul(C2(v[x[i]].size()-1),v[y[i]].size()-1)),
		Add(ans, mul(C2(v[y[i]].size()-1),v[x[i]].size()-1));
		Add(ans, Mod-mul(3,calc()));
		for(int i=1; i<=n; i++){
			int coe = 0;
			for(int e=0; e<v[i].size(); e++){
				int u = v[i][e];
				Add(ans,mul(coe, v[u].size()-1));
				Add(coe, v[u].size()-1);
			}
		} 
		Add(ans, Mod-mul(3,Circle4()));
		cout << ans; 
	}
}
int main(){
	n = read(), m = read(), k = read();
	for(int i = 1; i <= m; i++){
		x[i] = read(), y[i] = read();
		v[x[i]].push_back(y[i]);
		v[y[i]].push_back(x[i]);
	}
	if(k == 1){ cout << m; return 0; }
	if(k == 2){ Subtask2::Solve(); return 0;}
	if(k == 3){ Subtask3::Solve(); return 0;}
	if(k == 4){ Subtask4::Solve(); return 0;}
}