企业内部管理系统网站建设,网站建立企业,ui设计师培训班,网络网站开发培训题意
传送门 HDU 6391 Lord Li’s problem
题解
仅考虑 S i ≠ T i S_i\neq T_i SiTi 的数量 m m m#xff0c;最后答案除以 ( n m ) \binom{n}{m} (mn) 即可。考虑 X X X 的排列#xff0c;最后答案除以 k ! k! k! 即可。 d p [ i 1 ] [ j ] dp[i1][j] dp[…题意
传送门 HDU 6391 Lord Li’s problem
题解
仅考虑 S i ≠ T i S_i\neq T_i SiTi 的数量 m m m最后答案除以 ( n m ) \binom{n}{m} (mn) 即可。考虑 X X X 的排列最后答案除以 k ! k! k! 即可。 d p [ i 1 ] [ j ] dp[i1][j] dp[i1][j] 代表考虑 X 0 ⋯ X i X_0\cdots X_i X0⋯Xi这些数字异或和中 1 的数量为 j j j 情况下方案的数量。令 a , b a,b a,b 分别为将 X i X_i Xi 异或进来后异或和为 0 和 1 的数量对应的贡献为 d p [ i ] [ j ] ⋅ ( j a ) ⋅ ( n − j b ) dp[i][j]\cdot\binom{j}{a}\cdot\binom{n-j}{b} dp[i][j]⋅(aj)⋅(bn−j)。 X i X_i Xi 可以为任意数字那么要从 d p [ i 1 ] [ j ] dp[i1][j] dp[i1][j] 中减去 X i X_i Xi 之前出现过的情况对应的贡献为 d p [ i − 1 ] [ j ] ⋅ i ⋅ [ ( n 3 ) − ( i − 1 ) ] dp[i-1][j]\cdot i\cdot[\binom{n}{3}-(i-1)] dp[i−1][j]⋅i⋅[(3n)−(i−1)]。单个样例时间复杂度 O ( n k ) O(nk) 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];}vectorvectorll dp(k 1, vectorll(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;
}
