状压 dp 总结

三进制状压

Q&A

1.如果我的当前的dp值需要前两个状态才可以推导出来怎么办?

很简单,既然我们无法舍弃任何一个状态那我们就加一维将它纳入考虑范围之内,就拿 P8756 [蓝桥杯 2021 省 AB2] 国际象棋做列子
我们本列的马最远是可以威胁到前两列的马,那么我们就让 dp 表示这一列与上一列的马的情况,这样子转移就很明了了.

for(int i=1;i<=m;i++)
    for(int L=0;L<=(1<<n)-1;L++)
        for(int S=0;S<=(1<<n)-1;S++)
            for(int T=0;T<=(1<<n)-1;T++)
                dp[i][S][T]= contribution(dp[i-1][L][S]);//contribution()这个状态从上一个状态得到的贡献

值得注意的是这个数组肯定是要滚动的,不然爆空间是一件无疑的事情.
类似这样的题目

P2704	[NOI2001] 炮兵阵地
P8756	[蓝桥杯 2021 省 AB2] 国际象棋

2.如果数值太大我们的状态放不下怎么办?
3.如果要考虑

提出这么多个疑问都是为了引出这道题,因为实在觉得这道题出的太好了.

$P2150 [NOI2015] 寿司晚宴$

[NOI2015] 寿司晚宴

题目描述

为了庆祝 NOI 的成功开幕，主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手，也被邀请参加了寿司晚宴。

在晚宴上，主办方为大家提供了 $n−1$ 种不同的寿司，编号 $1,2,3,\ldots,n-1$，其中第 $i$ 种寿司的美味度为 $i+1$。（即寿司的美味度为从 $2$ 到 $n$）

现在小 G 和小 W 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 G 品尝的寿司种类中存在一种美味度为 $x$ 的寿司，小 W 品尝的寿司中存在一种美味度为 $y$ 的寿司，而 $x$ 与 $y$ 不互质。

现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数 $p$ 取模）。注意一个人可以不吃任何寿司。

输入格式

输入文件的第 $1$ 行包含 $2$ 个正整数 $n, p$ 中间用单个空格隔开，表示共有 $n$ 种寿司，最终和谐的方案数要对 $p$ 取模。

输出格式

输出一行包含 $1$ 个整数，表示所求的方案模 $p$ 的结果。

提示

【数据范围】

勘误：$0 < p \le 10^9 $

可以从题目中提炼出来的较为浅显的信息:

1.要求全部互质,也就是两人所选的数包括的质因数集合没有交集,可以考虑从这里下手做状态
2.n≤500,我们简单写个输出质因数表的暴力,发现有整整92个质因数,显然直接用来做状态是会爆的

好了,就这些信息了,没了...
大部分选手已经可以根据这些信息得到一个30pts的状压了但我太蒟了
程序实现时盯着自己的草稿纸半天都没有一点动作,看了题解之后还是决定把暴力也详细的推一遍.

我们令n位二进制数表示现在已经包括了x个质因数(有则1无则0),我们先预处理一遍所有数的质因数(把他们转成形如上文的二进制数)
我们对于每一道菜有3种可选的转移:

1.给小G
2.给小W
3.都不给

我们定义dp的第一维表示小G的状态,第二维表示小W的状态

就会有

$1.dp[i][G|a[i]][W]+=dp[i-1][G][W]$
$2.dp[i][G][W|a[i]]+=dp[i-1][G][W]$
$3.dp[i][G][W]+=dp[i-1][G][W]$

注意我们这里转移之前都需要先判断会不会$(G&a[i])$和$(W&a[i])$都是有值的,也就是说要小心不要让他们吃到有相同质因子的菜啦
暴力告一段落,下面我们开始讲正解,