无向图三元环计数
O(msqrt(m))O(m sqrt(m))O(msqrt(m))
ll solve(ll n,ll m)
{
ll a,b;
FOR(i,1,n)
{
RLL2(a,b);e.pb(P(a,b));
++d[a],++d[b];
}
FOR(i,1,m)
{
ll u = e[i].first,v = e[i].second;
if(d[u] < d[v] || (d[u] == d[v] && u > v)) swap(u,v);
G[u].pb(v);
}
ll ans = 0;
FOR(i,1,n)
{
for(auto u:G[i]) vis[u] = i;
for(auto u:G[i]) for(auto v:G[u]) if(vis[v] == i) ans++;
}
return ans;
}
有向图三元环计数
先将图转化为无向图,然后用无向图方法求出三元环,因为数量不超过O(msqrt(m))O(m sqrt(m))O(msqrt(m))
所以可以求出来以后在在原图上判断该三元环是否存在
竞赛图三元环计数
先考虑所有方案数,任选三点的方案数为Cn3C_n^3Cn3
然后去掉不合法的,对于一个点iii,不可能存在一个三元环,不可能存在两条出边来至该点
因此对于该点的方案数为 C∣d[i]∣2C_{|d[i]|}^2C∣d[i]∣2
所以总方案数为
Cn3−∑inC∣d[i]∣2C_n^3 - \sum_i^n C_{|d[i]|}^2
Cn3−i∑nC∣d[i]∣2
Read More ~
标签:#
模版
「Template」矩阵快速幂
一些经验
GCD(Fbi[x],Fbi[y])=Fbi[GCD(x,y)]GCD(Fbi[x],Fbi[y]) = Fbi[GCD(x,y)]GCD(Fbi[x],Fbi[y])=Fbi[GCD(x,y)]
f[i]=f[i−1]∗f[i−2]f[i] = f[i-1] * f[i-2]f[i]=f[i−1]∗f[i−2] 可以考虑指数上的增长
模版
// 假设 f[i] = f[i-1] + f[i-3]
// f[i] = f[i-1] * 1 + f[i-2] * 0 + f[i-3] * 1;
// f[i-1] = f[i-1] * 1 + f[i-2] * 0 + f[i-3] * 0;
// f[i-2] = f[i-1] * 0 + f[i-2] * 1 + f[i-3] * 0;
// 则矩阵设为
// [ 1 , 0 , 1 ]
// [ 1 , 0 , 0 ]
// [ 0 , 1 , 0 ]
// 设置M.init() , 第k项运行运行M.getans(k);
struct Matrix_Pow
{
ll n,mod;
struct matrix
{
long long a[100][100];
}ans,base;
inline void init() // 这部分设置初始值
{
}
matrix matrix_mul(matrix A, matrix B)
{
matrix C;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
{
C.a[i][j] = 0;
for (int k = 1; k <= n; ++k) C.a[i][j] = (C.a[i][j] + (A.a[i][k] * B.a[k][j] % mod)) % mod;
}
return C;
}
void matrix_pow(long long b)
{
for (; b; b >>= 1)
{
if (b & 1) ans = matrix_mul(ans, base);
base = matrix_mul(base, base);
}
}
}M;
Read More ~