标签:# 模版

「Template」三元环计数

无向图三元环计数 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∑n​C∣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 ~