PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Jatin Yadav
Tester: Alex Danilyuk
Editorialist: Jatin Yadav
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Inclusion-Exclusion Principle, Counting
PROBLEM:
Given a simple undirected graph. Count the sets of edges, which when added to the graph make it 2-regular.
EXPLANATION:
If the graph has any vertex of degree > 2, the answer is clearly 0. Otherwise, all degrees are \le 2 and the graph consists of singletons, chains and cycles.
Subtask 1
We have K = N(N-1)/2 - M edges that can be added to the graph. Consider any ordering e_1, e_2, ,\ldots e_K of these edges. The state of the graph can be represented a degree vector. So there are 3^n valid states (for each node, degree 0, 1 or 2) and we can define a simple recursion based on whether we add e_i or not. The time complexity would be O(N^2 3^N).
Subtask 2 and 3
Let there be a singletons, b chains of size 2 and c chains of size \geq 3 in the graph.
Define F(a, b, c) to be the number of sequences of edges we can add to a graph with a singletons, b chains of size 2 and c chains of size \geq 3 to make it 2-regular. Consider the first added edge. The following are the possibilities:
- The edge connects two endpoints of a single chain : c \times F(a, b, c-1)
- Two singletons : \binom{a}{2} \times F(a - 2, b + 1, c)
- Two chains of size 2 : 4 \times \binom{b}{2} \times F(a, b - 2, c + 1)
- Two chains of size \geq 3 : 4 \times \binom{c}{2} \times F(a, b, c - 1)
- A singleton and a chain of size 2 : 2 \times a b \times F(a - 1, b - 1, c +1)
- A singleton and a chain of size \geq 3 : 2 \times a c \times F(a - 1, b, c)
- A chain of size 2 and a chain of size \geq 3 : 4 \times bc \times F(a, b - 1, c)
In F(a, b, c) we have considered every valid edge set (a+b+c)! times, as the edges can be added in any order. So, the final answer is F(a, b, c)/(a+b+c)!
The time complexity here is O(N^3)
Code
int val(int A, int B, int C){
if(A + B + C == 0) return 1;
if(A + B + C == 1) return C == 1;
for(int a = 0; a <= A + B + C; a++)
for(int b = 0; a + b <= A + B + C; b++)
dp[a][b] = 0;
dp[0][0] = 1;
for(int s = 2; s <= A + B + C; s++){
for(int a = 0; a < s; a++){
for(int b = 0; a + b < s; b++){
dp2[a][b] = dp[a][b];
dp[a][b] = 0;
}
}
// a <= A
int mx_a = min(s, A);
for(int a = 0; a <= mx_a; a++){
int mx_b = min(B + A / 2, s - a);
for(int b = 0; b <= mx_b; b++){
ll ret = 0;
int c = s - a - b;
if(c) ret += c * 1LL * dp2[a][b];
if(a >= 2) ret += C2(a) * dp2[a - 2][b + 1];
if(b >= 2) ret += 4LL * C2(b) * dp2[a][b - 2];
if(c >= 2) ret += 4LL * C2(c) * dp2[a][b];
if(a && b) ret += 2LL * a * b * dp2[a - 1][b - 1];
if(a && c) ret += 2LL * a * c * dp2[a - 1][b];
if(b && c) ret += 4LL * b * c * dp2[a][b - 1];
dp[a][b] = ret % mod;
}
}
}
return dp[A][B];
}
Subtask 4
We are basically trying to make cycles from the chains in the original graph. Consider a singleton as a chain of size 1. Then in each cycle, the sum of the sizes of the chains used has to be \geq 3.
Consider those ways in which we end up with exactly k cycles. For each cycle, there are two ways of giving it a direction (clockwise or anticlockwise). So, we will consider directed cycles and divide by 2^k. Each ways of choosing directed cycles represents a permutation of the chains. We have to exclude cycles of 3 kinds in this permutation:
- Those consisting of two chains of size 1
- Those consisting a single chain of size 1
- Those consisting of a single chain of size 2.
For this, we will use inclusion exclusion. Let’s say we are excluding q particular cycles of the first kind. The number of ways to choose these is \binom{a}{2q} \times (2q-1) {!} {!}, as we can choose 2q individual chains in \binom{a}{2q} ways, and then group them in (2q-1) {!} {!} ways. After this, note that the chains of the second and third kind are similar (the only restriction is that they can’t be mapped to themselves). If there are a total p chains of second and third kind we’re excluding, we can choose them in \binom{a+b-2q}{p} ways. For the remaining a+b+c - p - 2q chains, we can have any permutation. If the remaining part had k cycles, we need to multiply by \dfrac{1}{2^{p+q+k}} as there are p+q+k total cycles. Also, we need to multiply by (-1)^{p+q} for the inclusion exclusion part.
Let F(n) be the sum of 2^{-\text{number of cycles}} over all permutations of n elements.
Then, F(n) = \dfrac{F(n - 1)}{2} + (n - 1) f(n-1) = (n - \frac{1}{2}) F(n - 1).
This is because, we can either map n to itself, increasing the number of cycles by 1 or we can map it to some of the other n-1 elements, keeping the number of cycles the same.
Then, our answer can be written as:
\displaystyle \sum_{q=0}^{a/2} \sum_{p=0}^{a+b-2q} (-1/2)^{p+q} \binom{a}{2q} \binom{a + b - 2q}{p} (2q-1) {!} {!} \text{ } F(a + b + c - p - 2q)
After precomputing factorials, double factorials and all the F values in O(N), the answer can be easily be found in O(N^2) by iterating on p and q.
Subtask 5
Let’s expand \binom{a + b - 2q}{p} in the above expression. Then the summand can be expressed as u_p \times v_q \times w_{p+2q}, where,
- u_p = (-1/2)^p \frac{x^p}{p!}
- v_q = (-1/2)^q \binom{a}{2q}(2q-1)!!(a+b-2q)!
- w_r = \frac{F(a + b + c - r)}{(a + b-r)!}
Consider U(x) = \displaystyle \sum_{p=0}^{a+b} u_px^p and V(x) = \displaystyle \sum_{q=0}^{a/2} v_q x^{2q}
Let c_r be the coefficient of x^r in A(x)B(x),
Then our answer is \displaystyle \sum_{r=0}^{a+b} c_r w_r
The time complexity is O(N \log(N))
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
#include <atcoder/convolution>
using namespace atcoder;
using mint = modint998244353;
const int N = 1 << 20;
mint fact[N], invfact[N], df[N];
const mint inv2 = (998244353+1)/2;
mint F[N], pow2[N];
void pre(){
fact[0] = pow2[0] = invfact[0] = 1;
df[0] = df[1] = 1;
for(int i = 1; i < N; i++){
fact[i] = fact[i - 1] * i;
invfact[i] = fact[i].inv();
pow2[i] = pow2[i - 1] * 2;
if(i > 1) df[i] = df[i - 2] * i;
}
// F-> no constraint
F[0] = 1; // can be computed in O(N) as well
for(int n = 1; n < N; n++){
F[n] = F[n - 1] * (n - inv2);
}
}
mint choose(int a, int b){
if(a < b || b < 0) return 0;
return fact[a] * invfact[b] * invfact[a - b];
}
mint fast(int a, int b, int c){
int n = a + b + c;
vector<mint> Q(a + 1);
vector<mint> P(a + b + 1);
mint pw2 = 1;
for(int q = 0; 2 * q <= a; q++){
Q[2 * q] = fact[a + b - 2 * q] * choose(a, 2 * q) * (q == 0 ? 1 : df[2 * q - 1]) * pw2;
pw2 *= -inv2;
}
pw2 = 1;
for(int p = 0; p <= a + b; p++){
P[p] = pw2 * invfact[p];
pw2 *= -inv2;
}
vector<mint> G = convolution(P, Q);
mint ans = 0;
for(int r = 0; r <= a + b; r++){
ans += G[r] * F[a + b + c - r] * invfact[a + b - r];
}
return ans * pow2[b + c];
}
int get(int n, vector<pair<int, int>> edges){
vector<vector<int>> adj(n);
for(auto it : edges){
adj[it.first].push_back(it.second);
adj[it.second].push_back(it.first);
}
vector<int> vis(n);
int a = 0, b = 0, c = 0;
for(int i = 0; i < n; i++) if(sz(adj[i]) > 2) return 0;
for(int i = 0; i < n; i++){
if(vis[i]) continue;
int d = sz(adj[i]);
if(d == 0){
a++;
continue;
}
if(d == 2) continue;
int k = i, num = 0;
while(k != -1){
vis[k] = 1;
num++;
int _k = -1;
for(int v : adj[k]) if(!vis[v]){
_k = v;
break;
}
k = _k;
}
if(num==2) b++;
else c++;
}
return fast(a, b, c).val();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); // Remove in interactive problems
pre();
int t; cin >> t;
while(t--){
int n, m;
cin >> n >> m;
vector<pair<int, int>> edges(m);
for(int i = 0; i < m; i++){
cin >> edges[i].first >> edges[i].second;
edges[i].first--; edges[i].second--;
}
cout << get(n, edges) << endl;
}
}
Tester's Solution
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const ll MOD = (ll)1e9 + 7;
ll add(ll x, ll y) {
x += y;
if (x >= MOD) return x - MOD;
return x;
}
ll sub(ll x, ll y) {
x -= y;
if (x < 0) return x + MOD;
return x;
}
ll mult(ll x, ll y) {
return (x * y) % MOD;
}
ll bin_pow(ll x, ll p) {
if (p == 0) return 1;
if (p & 1) return mult(x, bin_pow(x, p - 1));
return bin_pow(mult(x, x), p / 2);
}
ll rev(ll x) {
return bin_pow(x, MOD - 2);
}
const int N = 5010;
int C[N][N];
int f[N], ff[N];
int rp2[N];
vector<int> g[N];
bool used[N];
vector<int> all;
int n;
int a, b, c;
void dfs(int v) {
used[v] = 1;
all.push_back(v);
for (int u : g[v])
if (!used[u])
dfs(u);
}
void solve() {
int m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
g[i].clear();
used[i] = false;
}
for (int i = 0; i < m; i++) {
int v, u;
scanf("%d%d", &v, &u);
v--;u--;
g[v].push_back(u);
g[u].push_back(v);
}
a = b = c = 0;
for (int i = 0; i < n; i++) {
if ((int)g[i].size() > 2) {
printf("0\n");
return;
}
}
for (int v = 0; v < n; v++) {
if (used[v]) continue;
all.clear();
dfs(v);
bool cyc = true;
for (int x : all)
cyc &= (int)g[x].size() == 2;
if (cyc) continue;
if ((int)all.size() == 1) {
a++;
} else if ((int)all.size() == 2) {
b++;
} else {
c++;
}
}
int ans = 0;
for (int x = 0; 2 * x <= a; x++)
for (int y = 0; y <= a + b - 2 * x; y++) {
ans = add(ans, mult(mult(C[a][2 * x], ff[x]), mult(mult(C[a + b - 2 * x][y], rp2[x + y]), f[a + b + c - 2 * x - y])));
}
for (int i = 0; i < b + c; i++)
ans = add(ans, ans);
int F = 1;
for (int i = 1; i <= n; i++)
F = mult(F, i);
for (int i = 0; i < 2 * n; i++)
ans = mult(ans, F);
printf("%d\n", ans);
}
int main()
{
startTime = clock();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
for (int i = 0; i < N; i++)
C[i][0] = C[i][i] = 1;
for (int i = 1; i < N; i++)
for (int j = 1; j < i; j++)
C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
f[0] = 1;
int cur = (MOD + 1) / 2;
for (int i = 1; i < N; i++) {
f[i] = mult(f[i - 1], cur);
cur = add(cur, 1);
}
ff[0] = 1;
for (int i = 1; i < N; i++) {
ff[i] = mult(ff[i - 1], 2 * i - 1);
}
rp2[0] = 1;
for (int i = 1; i < N; i++) {
rp2[i] = rp2[i - 1];
if (rp2[i] & 1) rp2[i] += MOD;
rp2[i] /= 2;
rp2[i] = sub(0, rp2[i]);
}
int t;
scanf("%d", &t);
while(t--) solve();
return 0;
}