本文主要是介绍BJ模拟（2） D3T1 and，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
and
题目背景：
thoj28
分析：我可能是个智障吧·····这是我在集训时做过的一道原题，然后我竟然连看都没有看出来，考试强行一波暴力，我想我还是比较适合回家种田······这是一道优秀的dp，考虑将所有的数取反，那么约束就变成了：所有的数or起来等于2w –1，且去掉任何一个都不满足条件，因为这个题我也没有想太清楚，可能就只能直接给出结论了，我们如果选出的某个树x不满足条件，那么x之前所选的数的or我们可以知道，我们知道其他的数的or会覆盖他，导致不合法，所以后面的or应该是(x – (x & pre))的超集。
令f[i][j][k]表示考虑了前i个，or为j，后面选的数的or为k的超集的方案。
第一种转移: 不选：f[i][j][k] à f[i +1][j][k]
第二种转移：选，不强制违法：f[i][j][k]à f[i + 1][j | a[i + 1]][k –(k & a[i + 1])]
第二种转移：选，强制违法：-f[i][j][k]à f[i + 1][j | a[i + 1]][(k –(k & a[i + 1])) | (a[i + 1] – (a[i + 1] & j))]
因为容斥定理，第三种违法转移系数为-1。显然第三维是第二维的子集，那么复杂度就是O(n * 3w)了。
Source：
#include #include #include #include #include #include #include using namespace std; const int mod = 1e9 + 7; const int MAXN = 50 + 10; const int MAXM = 10000 + 10; const int M = 8192; int n, t; int a[MAXN]; int dp[2][MAXM][MAXM]; inline char read() { static const int IN_LEN = 1024 * 1024; static char buf[IN_LEN], *s, *t; if (s == t) { t = (s = buf) + fread(buf, 1, IN_LEN, stdin); if (s == t) return -1; } return *s++; } template inline bool R(T &x) { static char c; static bool iosig; for (c = read(), iosig = false; !isdigit(c); c = read()) { if (c == -1) return false; if (c == '-') iosig = true; } for (x = 0; isdigit(c); c = read()) x = (x << 3) + (x << 1) + (c ^ '0'); if (iosig) x = -x; return true; } const int OUT_LEN = 1024 * 1024; char obuf[OUT_LEN], *oh = obuf; inline void writechar(char c) { if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf; *oh++ = c; } template inline void W(T x) { static int buf[30], cnt; if (!x) writechar(48); else { if (x < 0) writechar('-'), x = -x; for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48; while (cnt) writechar(buf[cnt--]); } } inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); } void readin() { R(n); for(int i = 1; i <= n; ++i) R(a[i]), a[i] = M - 1 - a[i]; } void add(int &x, int y) { x += y; if (x >= mod) x -= mod; } void work() { dp[0][0][0] = 1; int x = 0; for (int i = 0; i <= n; ++i) { for (int j = 0; j < M; ++j) for (int k = j; ; (--k) &= j) { if(dp[x][j][k]) add(dp[x ^ 1][j][k], dp[x][j][k]); if((a[i + 1] & j) ^ a[i + 1]) { add(dp[x ^ 1][j | a[i + 1]][k ^ (k & a[i + 1])], dp[x][j][k]); add(dp[x ^ 1][j | a[i + 1]][(k ^ (k & a[i + 1])) | (a[i + 1] ^ (a[i + 1] & j))], -dp[x][j][k]); } if (i != n) dp[x][j][k] = 0; if(!k) break; } x ^= 1; } W(dp[x][M - 1][0]); } int main() { // freopen("in.in", "r", stdin); readin(); work(); flush(); return 0; }
这篇关于BJ模拟（2） D3T1 and的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
