HDU多校第七场 1008 Heart —— 子集dp + 卡常

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $n$ 条弹幕，每条弹幕有两个值 $p$ 和 $b$
    $p$ 代表攻击力，$b$ 代表由其二进制构成这条弹幕
    一个必杀技 $A$ 是 $n$ 条弹幕的子集，且满足 $u,v\in A,u?=v,b_u\cap b_v=?$
    定义 $S(A)={\cup }_{u\in A}{b}_u$，$A$ 的攻击力为其所有弹幕的攻击力的乘积
    $m$ 次查询，每次查询 $x$，求所有 $A$ 的攻击力和，且 $S(A)=x$

解题思路：

    因为 $0\le b_i<2^{21}$，顺而想到子集 $dp$
    设 $dp[i]$ 为 $S(A)=i$ 时所有 $A$ 的攻击力和
    $dp[i]+=dp[j]?dp[k]，j?k=i，j\&k=0$
    然而这样计算的时间复杂度是 $3^{21}$，本地跑远超过 $20$ 秒
    而且这样计算会重复计算，设 $f[i]$ 为只由一条弹幕组成 $i$ 的攻击力
    那么 $dp[i]+=f[j]?dp[k]，j?k=i，j\&k=0$
    这样直接枚举所有子集仍然会重复计算，那么考虑限制一下 $j$
    设 $lowbit(i)=lb$，我们确保枚举的 $j$ 满足 $j\&lb=lb$
    也就是将 $i$ 的最低位给取出来，$j$ 的这一位始终为 $1$，其他位继续枚举

    这样就完美的解决了重复计算的问题，而且因为枚举的子集状态位少了一位
    时间复杂度大概为 $3^{20}$，当时测试了一下大概要 $60$ 秒左右，但是要优化到 $20$ 秒内
    简单的输入输出挂，变量名放到外面什么相信大家都会，然而这优化不了几秒，其他卡常方法如下：

    采用快速取模
    考虑将 $dp$ 数组设为 $long$ $long$，作乘的时候必须取模，但作加的时候就可以直接加，枚举完所有子集后再取模
    因为 $j$ 始终包含了 $i$ 的最低位，那么 $dp[k]$ 就始终缺少这一位
    那么也就意味着，我们不需要处理所有的 $dp$ 值，因为有的 $dp$ 值不可能用到
    这些不可能用到的 $dp$ 值就是 $i$ 为奇数的情况，因为 $dp[k]$ 的 $k$ 始终为偶数
    但是如果查询的 $x$ 为奇数，我们就必须处理 $dp[x]$
    因此考虑将查询离线，将出现过的 $x$ 记录为 $vis[x]=1$
    若 $i$ 为奇数且 $vis[x]=0$，代表这个 $dp[i]$ 可以直接跳过
    我们假设出题人的数据是随机造的，时间复杂度就会降到 $3^{20}\times \frac{3}{4}$
    全部优化后本题只需要 $18$ 秒内就能搞定！！！
    就不用学子集卷积了

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 1 << 23;
const int mod = 998244353;
int n, m, ans[maxn];
ll dp[maxn], f[maxn];const int MAXSIZE=100000;
char buf[MAXSIZE],*p1=buf,*p2=buf;
#define nc p1==p2&&(p2=(p1=buf)+fread\
(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++
inline void read(int &x) {bool f=0; char ch=nc; x=0;while(!isdigit(ch)) {if(ch=='-')f=1;ch=nc;}while(isdigit(ch)) x=x*10+ch-'0',ch=nc;if(f) x=-x;
}typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {ull b, m;FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}inline ull reduce(const ull a) { return a - (ull)((L(m) * a) >> 64) * b;}
} F(mod);int f0 = 1, tmp, i, j, p, b, qry[maxn], vis[maxn];
int lb, now, mx = 1 << 21, x, jlb;
signed main() {read(n);for( i=1; i<=n; ++i) {read(p), read(b);if(b == 0) f0 = F.reduce(1ll * f0 * (1 + p));else {tmp = f[b] + p;if(tmp >= mod) dp[b] = f[b] = tmp - mod;else dp[b] = f[b] = tmp;}}dp[0] = 1; // 2097152read(m);for( i=1; i<=m; ++i) read(qry[i]), vis[qry[i]] = 1;for( i=1; i<mx; ++i) {if((i&1) && !vis[i]) continue;lb = i & (-i), now = i ^ lb;for( j=(now-1)&now; j; j=(j-1)&now) {jlb = j + lb;dp[i] += F.reduce(f[jlb] * dp[i - jlb]);}if (lb != i) dp[i] += F.reduce(f[lb] * dp[i - lb]);dp[i] = F.reduce(dp[i]);}for( i=1; i<=m; ++i) {x = qry[i];if(x == 0) ans[i] = F.reduce(f0 - 1 + mod);else ans[i] = F.reduce(dp[x] * f0);printf("%d\n", ans[i]);}
}