FWT优化求教
  • 板块学术版
  • 楼主DesserTy
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/3/22 00:03
  • 上次更新2024/3/22 14:45:17
查看原帖
FWT优化求教
711880
DesserTy楼主2024/3/22 00:03

https://www.cnblogs.com/rikurika/p/13370358.html 这篇文章里是xor的fwt优化,and和or的fwt要怎么计算?比如下面这段代码

// n <= 2e5, m <= 17
vector<int> dp(1 << m);
dp.back() = 1;
for (int i = 0; i < n; i++) {
    int mask = 0;
    // ...计算 mask
    auto ndp = dp;
    for (int j = 0; j < (1 << m); j++) {
        ndp[i & mask] += dp[i];
    }
    dp = ndp;
}
2024/3/22 00:03
加载中...