[NOI2015]寿司晚宴

Portal

这题目真是神题.

因为a, b互质,那就代表a,b的质因数分解的素数集合交集是空集.

那么只要两者的集合的质因数分解的素数集是空集合.

考虑每个数最多只有1个超过\(\sqrt{n}\)的因子, 那么这样算\(\sqrt{n}\)以内最多有8个质数.

然后我们直接状压Dp. 把大于等于22的大素因子单独提出来, 按照这个进行处理.

设dp[i][j][k]表示计算到第i个数字, 甲的状态为j,乙的状态为k, 这里空间太小开不下, 所以滚动第一维.

这里有一个小trick,因为有部分数的最大素因子是相同的, 所以我们可以一起处理, 不用拷贝数组, 这样只要排一发序就可以了.

细节: 枚举状态的时候必须从大到小枚举, 这里和01背包的原因相同.

Code

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(LL i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(LL i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprLLf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
LL read() {
    char ch = getchar();
    LL x = 0, flag = 1;
    for (;!isdigit(ch); ch = getchar()) if (ch == ‘-‘) flag *= -1;
    for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x * flag;
}
void write(LL x) {
    if (x < 0) putchar(‘-‘), x = -x;
    if (x >= 10) write(x / 10);
    putchar(x % 10 + 48);
}

const LL Maxn = 509, primes[9] = {0, 2, 3, 5, 7, 11, 13, 17, 19}, MaxMask = 301;
static LL n, Mod;

void add(LL &x, LL y) {
    if (y >= Mod) y -= Mod;
    if (y < 0) y += Mod;
    x += y;
    if (x >= Mod) x -= Mod;
}

struct node {
    LL mask, bigger;
    LL operator < (const node &s) const { return bigger < s.bigger; }
}s[Maxn];

void separate(LL Num) {
    LL Index = Num - 1;
    rep (i, 1, 8) {
        if (Num % primes[i]) continue;
        s[Index].mask |= 1 << (i - 1);
        while (!(Num % primes[i])) Num /= primes[i];
    }
    s[Index].bigger = Num;
}

void init() {
    n = read(), Mod = read();
    rep (i, 1, n - 1) separate(i + 1);
}

static LL dp[MaxMask][MaxMask], f[2][MaxMask][MaxMask];
int cmp(node a, node b) { return a.bigger > b.bigger;}

void solve() {
    sort(s + 1, s + n);

    dp[0][0] = 1;
    rep (i, 1, n - 1) {
        if (i == 1 || s[i - 1].bigger != s[i].bigger || s[i].bigger == 1) {
            memcpy(f[0], dp, sizeof dp);
            memcpy(f[1], dp, sizeof dp);
        }

        drep (j, MaxMask - 1, 0)
            drep (k, MaxMask - 1, 0) {
                if (j & k) continue;
                if ((k & s[i].mask) == 0) add(f[0][j | s[i].mask][k], f[0][j][k]);
                if ((j & s[i].mask) == 0) add(f[1][j][k | s[i].mask], f[1][j][k]);
            }

        if (i == n - 1 || s[i + 1].bigger != s[i].bigger || s[i].bigger == 1) {
            rep (j, 0, MaxMask - 1)
                rep (k, 0, MaxMask - 1) {
                    if (j & k) continue;
                    dp[j][k] = (f[0][j][k] + f[1][j][k] - dp[j][k] + Mod) % Mod;
                }
        }
    }
    
    LL ans = 0;
    rep (i, 0, MaxMask - 1)
        rep (j, 0, MaxMask - 1) 
            if ((i & j) == 0) (ans += dp[i][j]) %= Mod;
            
    cout << ans << endl;
}

int main() {
//  freopen("LG2150.in", "r", stdin);
//  freopen("LG2150.out", "w", stdout);

    init();
    solve();

#ifdef Qrsikno
    debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
    return 0;
}

[NOI2015]寿司晚宴

原文：https://www.cnblogs.com/qrsikno/p/10246680.html