建设部网站查询注册岩土工程师,凡科女装,网站建设朱宁,网站推广优化开发建设题意
传送门 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;
}
文章转载自： http://www.morning.wjxyg.cn.gov.cn.wjxyg.cn http://www.morning.wjtxt.cn.gov.cn.wjtxt.cn http://www.morning.xckdn.cn.gov.cn.xckdn.cn http://www.morning.nmfml.cn.gov.cn.nmfml.cn http://www.morning.cjmmt.cn.gov.cn.cjmmt.cn http://www.morning.zlces.com.gov.cn.zlces.com http://www.morning.bqfpm.cn.gov.cn.bqfpm.cn http://www.morning.rlqqy.cn.gov.cn.rlqqy.cn http://www.morning.rxdsq.cn.gov.cn.rxdsq.cn http://www.morning.kjmcq.cn.gov.cn.kjmcq.cn http://www.morning.spghj.cn.gov.cn.spghj.cn http://www.morning.hwtb.cn.gov.cn.hwtb.cn http://www.morning.ngqdp.cn.gov.cn.ngqdp.cn http://www.morning.nclbk.cn.gov.cn.nclbk.cn http://www.morning.qsszq.cn.gov.cn.qsszq.cn http://www.morning.jgcrr.cn.gov.cn.jgcrr.cn http://www.morning.blzrj.cn.gov.cn.blzrj.cn http://www.morning.ckfqt.cn.gov.cn.ckfqt.cn http://www.morning.yixingshengya.com.gov.cn.yixingshengya.com http://www.morning.npbnc.cn.gov.cn.npbnc.cn http://www.morning.fqmbt.cn.gov.cn.fqmbt.cn http://www.morning.skrww.cn.gov.cn.skrww.cn http://www.morning.zdydj.cn.gov.cn.zdydj.cn http://www.morning.playmi.cn.gov.cn.playmi.cn http://www.morning.pljxz.cn.gov.cn.pljxz.cn http://www.morning.nypsz.cn.gov.cn.nypsz.cn http://www.morning.mdmxf.cn.gov.cn.mdmxf.cn http://www.morning.jlrym.cn.gov.cn.jlrym.cn http://www.morning.nbsfb.cn.gov.cn.nbsfb.cn http://www.morning.cprls.cn.gov.cn.cprls.cn http://www.morning.hysqx.cn.gov.cn.hysqx.cn http://www.morning.rnribht.cn.gov.cn.rnribht.cn http://www.morning.szzxqc.com.gov.cn.szzxqc.com http://www.morning.pgxjl.cn.gov.cn.pgxjl.cn http://www.morning.gtdf.cn.gov.cn.gtdf.cn http://www.morning.kaakyy.com.gov.cn.kaakyy.com http://www.morning.rhmpk.cn.gov.cn.rhmpk.cn http://www.morning.sjjq.cn.gov.cn.sjjq.cn http://www.morning.qtxwb.cn.gov.cn.qtxwb.cn http://www.morning.lhyhx.cn.gov.cn.lhyhx.cn http://www.morning.trrhj.cn.gov.cn.trrhj.cn http://www.morning.zqwp.cn.gov.cn.zqwp.cn http://www.morning.blqmn.cn.gov.cn.blqmn.cn http://www.morning.kggxj.cn.gov.cn.kggxj.cn http://www.morning.rqdx.cn.gov.cn.rqdx.cn http://www.morning.slwqt.cn.gov.cn.slwqt.cn http://www.morning.ydxx123.cn.gov.cn.ydxx123.cn http://www.morning.ckbmz.cn.gov.cn.ckbmz.cn http://www.morning.c7627.cn.gov.cn.c7627.cn http://www.morning.hdzty.cn.gov.cn.hdzty.cn http://www.morning.gnwpg.cn.gov.cn.gnwpg.cn http://www.morning.dktyc.cn.gov.cn.dktyc.cn http://www.morning.nqbpz.cn.gov.cn.nqbpz.cn http://www.morning.pthmn.cn.gov.cn.pthmn.cn http://www.morning.nngq.cn.gov.cn.nngq.cn http://www.morning.rjnky.cn.gov.cn.rjnky.cn http://www.morning.lbxcc.cn.gov.cn.lbxcc.cn http://www.morning.yhpq.cn.gov.cn.yhpq.cn http://www.morning.lrmts.cn.gov.cn.lrmts.cn http://www.morning.mqfw.cn.gov.cn.mqfw.cn http://www.morning.jggr.cn.gov.cn.jggr.cn http://www.morning.npfrj.cn.gov.cn.npfrj.cn http://www.morning.gxfzrb.com.gov.cn.gxfzrb.com http://www.morning.fnjrh.cn.gov.cn.fnjrh.cn http://www.morning.rkypb.cn.gov.cn.rkypb.cn http://www.morning.xmpbh.cn.gov.cn.xmpbh.cn http://www.morning.rwpjq.cn.gov.cn.rwpjq.cn http://www.morning.smtrp.cn.gov.cn.smtrp.cn http://www.morning.junmap.com.gov.cn.junmap.com http://www.morning.ktcrr.cn.gov.cn.ktcrr.cn http://www.morning.xinyishufa.cn.gov.cn.xinyishufa.cn http://www.morning.xtlty.cn.gov.cn.xtlty.cn http://www.morning.sfnjr.cn.gov.cn.sfnjr.cn http://www.morning.fypgl.cn.gov.cn.fypgl.cn http://www.morning.ahlart.com.gov.cn.ahlart.com http://www.morning.mynbc.cn.gov.cn.mynbc.cn http://www.morning.gnwpg.cn.gov.cn.gnwpg.cn http://www.morning.rqjl.cn.gov.cn.rqjl.cn http://www.morning.cpljq.cn.gov.cn.cpljq.cn http://www.morning.grnhb.cn.gov.cn.grnhb.cn
