L - Sub-cycle Graph

Basic Information

Contest	The 2018 ICPC Asia Qingdao Regional Contest
Team AC Ratio	23/373 (6.2%)

Tutorial

A graph is a sub-cycle graph, if every connected component is either a single vertex or a chain. Of course, if this graph is actually a big cycle, it is also a sub-cycle graph. Let's first deal with some special cases:

$m = 0$ , these is only one such graph.
$m > n$ , no solution.
$m = n$ , all vertices must form a big cycle. Without loss of generality, let vertex $1$ be the "beginning" of the cycle, it is not hard to calculate that there are $\frac{(n - 1)!}{2}$ ways to form a cycle. We divide $2$ here because the cycle is not directional.

What remains is the case where $1 \leq m < n$ . Because there is no cycle in each connected component, we have $(n - m)$ connected components.

We enumerate $i$ from $1$ to $(n - m)$ , indicating that there are $i$ chains in these connected components (that is to say, there are $(n - m - i)$ single vertex), and we choose $2 i$ vertices as the endpoints of the chains. The number of ways to divide $2 i$ vertices into $i$ groups where each group has exactly $2$ vertices (that is, the number of ways to put $2 i$ different balls into $i$ indistinguishable boxes) can be calculated as

\prod_{k = 1}^{i} (2 k - 1)

You can imagine the grouping process like this: after sorting the $2 i$ vertices, each time group the smallest vertex and another vertex together. Thus the number of ways is $(2 i - 1) \times (2 i - 3) \times \dots$ .

Next, we need to distribute all vertices, except the vertices which form a connected component by themselves and the endpoints of the chains, into the chains. Because the order of vertices in a chain is crucial, we first choose a permutation of the vertices, and then divide them into $i$ groups where empty groups are allowed (that is, insert $(i - 1)$ partitions among $(m - i)$ balls). The number of ways can be calculated as

(m - i)! \times (\binom{m - 1}{i - 1})

So the final answer is

\sum_{i = 1}^{n - m} (\binom{n}{n - m - i}) \times (m - i)! \times (\binom{m - 1}{i - 1}) \times (\binom{m + i}{2 i}) \times \prod_{k = 1}^{i} (2 k - 1)

The time complexity is $O (n)$ .

Solution

#include <bits/stdc++.h>
#define MAXN ((int) 1e5)
#define MOD ((int) 1e9 + 7)
using namespace std;

int n;
long long ans, m;

long long fac[MAXN + 10], ifac[MAXN + 10];

long long C(int a, int b) {
    return fac[a] * ifac[b] % MOD * ifac[a - b] % MOD;
}

void solve() {
    scanf("%d%lld", &n, &m);
    if (m == 0) printf("1\n");
    else if (m > n) printf("0\n");
    else if (m == n) printf("%lld\n", fac[n - 1] * ifac[2] % MOD);
    else {
        ans = 0;
        // f is the \prod in the tutorial
        long long f = 1;
        for (int i = 1; i <= n - m; i++) {
            if (m + i < i * 2) continue;
            long long t = C(m + i, i * 2) * f % MOD;
            f = f * (i * 2 + 1) % MOD;
            t = t * fac[m - i] % MOD;
            t = t * C(m - 1, i - 1) % MOD;
            ans = (ans + C(n, n - m - i) * t) % MOD;
        }
        printf("%lld\n", ans);
    }
}

int main() {
    fac[0] = 1;
    for (int i = 1; i <= MAXN; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[0] = ifac[1] = 1;
    for (int i = 2; i <= MAXN; i++) ifac[i] = (MOD - MOD / i) * ifac[MOD % i] % MOD;
    for (int i = 2; i <= MAXN; i++) ifac[i] = ifac[i - 1] * ifac[i] % MOD;

    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}