题解：P11316 [RMI 2021] 去 M / NoM

· · 题解

来一个不要容斥的做法。

标号可以最后再乘，问题变为 2n 个点两两配对，配对的距离不是 m 倍数的方案数，等价于不能让模 m 同余的配对。

设 f_{i,j} 表示前 i 个同余类，总共有 j 个要和后面的配对，的方案数。 设第 i 个同余类有 c_{i} 个点。转移就枚举第 i+1 个同余类和前面配多少对，对于 k\in [0,\min(j,c_{i+1})]，

f_{i,j}\binom{c_{i+1}}{k}\binom{j}{k}k! \to f_{i+1,j-k+c_{i+1}-k}

每对的颜色有 2 种选择，编号是一个排列，答案就是 f_{m,0}2^{n}n!。

因为 \sum c_i = n，所以复杂度是 O(n^2)。

rep(i, 1, 2 * n)cnt[i % m]++;
f[0][0] = 1;
int sum = 0;
rep(i, 0, m - 1) {
    rep(j, 0, sum)if (f[i][j]) {
        rep(k, 0, min(j, cnt[i])) {
            add(f[i + 1][j + cnt[i] - 2 * k], 1LL * f[i][j] * C(cnt[i], k) % mod * C(j, k) % mod * fac[k] % mod);
        }
    }
    sum += cnt[i];
}
printf("%d", 1LL * f[m][0] * qpow(2, n) % mod * fac[n] % mod);