题解：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)

。

CPP

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);

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

文章操作

相关推荐

评论

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