HDU 6391 组合数学 + DP

题意

传送门 HDU 6391 Lord Li’s problem

题解

仅考虑 $S_i\ne T_i$ 的数量 $m$，最后答案除以 $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ 即可。考虑 $X$ 的排列，最后答案除以 $k!$ 即可。

$dp[i+1][j]$ 代表考虑 $X_0\cdots X_i$，这些数字异或和中 1 的数量为 $j$ 情况下方案的数量。令 $a,b$ 分别为将 $X_i$ 异或进来后，异或和为 0 和 1 的数量，对应的贡献为 $dp[i][j]\cdot \left(\genfrac{}{}{0ex}{}{j}{a}\right)\cdot \left(\genfrac{}{}{0ex}{}{n-j}{b}\right)$。$X_i$ 可以为任意数字，那么要从 $dp[i+1][j]$ 中减去 $X_i$ 之前出现过的情况，对应的贡献为 $dp[i-1][j]\cdot i\cdot [(\genfrac{}{}{0ex}{}{n}{3})-(i-1)]$。单个样例时间复杂度 $O(nk)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MOD = 19260817;
constexpr int N = 42;
ll fac[N], inv[N], invf[N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);fac[0] = invf[0] = 1;fac[1] = inv[1] = invf[1] = 1;for (int i = 2; i < N; ++i) {fac[i] = fac[i - 1] * i % MOD;inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;invf[i] = invf[i - 1] * inv[i] % MOD;}auto get = [&](int n, int m) -> ll {if (n < 0 || m < 0 || n < m) {return 0;}return fac[n] * invf[m] % MOD * invf[n - m] % MOD;};auto power = [&](ll x, int n) -> ll {ll res = 1;while (n > 0) {if (n & 1) {(res *= x) %= MOD;}(x *= x) %= MOD, n >>= 1;}return res;};int n, k, tt = 0;while (cin >> n >> k) {tt += 1;if (n == 0 && k == 0) {break;}string s, t;cin >> s >> t;int m = 0;for (int i = 0; i < n; ++i) {m += s[i] != t[i];}vector<vector<ll>> dp(k + 1, vector<ll>(n + 1));dp[0][0] = 1;for (int i = 0; i < k; ++i) {for (int j = 0; j <= n; ++j) {for (int a = 0; a <= 3; ++a) {int b = 3 - a;int nxt = j + (b - a);if (0 <= nxt && nxt <= n) {(dp[i + 1][nxt] += dp[i][j] * get(j, a) % MOD * get(n - j, b) % MOD) %= MOD;}}}if (i - 1 >= 0) {for (int j = 0; j <= n; ++j) {dp[i + 1][j] -= dp[i - 1][j] * i % MOD * (get(n, 3) - (i - 1)) % MOD;(dp[i + 1][j] += MOD) %= MOD;}}}ll res = dp[k][m];(res *= invf[k]) %= MOD;(res *= power(get(n, m), MOD - 2)) %= MOD;cout << "Case #" << tt << ": " << res << '\n';}return 0;
}