上一场多校一道状压DP的原题。
那我肯定是去做原题啦。

多校的时候我还觉得这肯定是许学姐的锅,没想到居然能转化成状压。

题意:
中文题面,给你[ 2, n ] 这几个数,要你各找两组数字,两组数字之间两两互质。
n 最大为500,问组合数量。

思路:
考虑数据 n 非常小,在 \sqrt 500以内的质数只有8个,而大于\sqrt 500的大元素只可能为一个,那么我们把相同的大元素放在一起处理,开一个二维数组表示这个大元素在两组中的哪一组,而对于小元素,可以用状态压缩来表示两组数字各自包含那几个质数。最后累加的时候让两个状态不重叠即可。

代码中 dp [ k ] [ a ] [ b ] [ c ] 表示 前k个元素中 第一组数包含的小质数状态为a ,第二组数包含的小质数状态为b ,大质数为在第一组0 ,或者在第二组1 的组合数量。
dp过程中,可以通过类似背包处理,反向计算,省掉一维。

f [ k ] [ a ] [ b ] 表示前k 个元素中,第一组包含的小质数状态为a,第二组包含的小质数状态为 b 的组合数量。

因为dp数组包含了当前大质数的分配状态。所以在处理不同大质数的时候理所当然地要将 dp数组重置。方法就是用f [ a ] [ b ]进行汇总,再分配。
在汇总的时候格外要注意的是,必须减去一个以前的f [ a ] [ b ],因为 dp数组在大质数分配的两个状态中都记录了以前的f [ a ] [ b ],也就是在此之上没有加上任何元素的组合数。汇总的时候是多加一次的,这应该比较容易理解。

而状态转移方程是最好理解,我就不多说了 虽然不是我想出来的

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 510;
const int maxc = 1 << 8;

ll dp[maxc][maxc][2], f[maxc][maxc];
ll n, mod;
int pri[10] = { 2, 3, 5, 7, 11, 13, 17, 19, 0, 0 };

struct node {
    int state;
    int big;
    bool operator<(const node& a) const { return big < a.big; }
} num[maxn];

void init()
{
    range(i, 2, n)
    {
        int x = i, v;
        each(j, 8) if (x % (v = pri[j]) == 0)
        {
            while (x % v == 0)
                x /= v;
            num[i].state |= (1 << j);
        }
        num[i].big = x;
    }
    sort(num + 2, num + n + 1);
    f[0][0] = 1;
}

int main()
{
    scanf("%lld %lld", &n, &mod);
    init();
    range(i, 2, n)
    {
        if (i == 2 || num[i].big == 1 || num[i].big != num[i - 1].big)
            reach(j, maxc) reach(k, maxc) dp[j][k][0] = dp[j][k][1] = f[j][k];
        reach(j, maxc) reach(k, maxc)
        {
            if ((num[i].state & j) == 0)
                dp[j][k | num[i].state][1] = (dp[j][k | num[i].state][1] + dp[j][k][1]) % mod;
            if ((num[i].state & k) == 0)
                dp[j | num[i].state][k][0] = (dp[j | num[i].state][k][0] + dp[j][k][0]) % mod;
        }
        if (i == n || num[i].big == 1 || num[i].big != num[i + 1].big)
            reach(j, maxc) reach(k, maxc) f[j][k] = (dp[j][k][0] + dp[j][k][1] - f[j][k] + mod) % mod;
    }
    ll ans = 0;
    reach(i, maxc) reach(j, maxc) if ((i & j) == 0) ans = (ans + f[i][j]) % mod;
    printf("%lld\n", ans);
    return 0;
}
Categories: 状压DP

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

状压DP

HDU 4628 Pieces

CLS的状压DP系列…… 然而实际上也算是一道简单题,但是我并没有立刻 Read more…

状压DP

状压DP 再入门 !!!

昨天写状压DP被煞笔天海和死肥宅带鱼嘲笑了 Damn! 然而事实也是一 Read more…

状压DP

CodeForces 11D A Simple Task

今天做的不太一样的状压,从去年的专题找的,看到学长并没有写是已经写过了 Read more…