【题解】LOJ 2131 「NOI2015」寿司晚宴

Problem

有 $n-1$ 个物品,权值依次为 $2,3,\cdots,n$

现两人各选择一些物品,不能有两个物品 $a,b$ 分别被两人选择并且 $a,b$ 不互质,求共有多少种选择方案

Thought

注意到 $23*23=529>500$ ,所以说我们确定了前面 $2,3,5,7,11,13,17,19$ 这几个质数组成的数之后,剩下数的必然包含且仅包含一个大质数

考虑按照大质数进行分组,某组拥有同一个大质数的数子显然仅能够被一个人选

令 $f[A][B]$ 为第一人选择集合为 $A$ ,第二人选择集合为 $B$ 的方案数

对于没有 $\geq 23$ 的质因子的数,直接往里怼进行更新
对于有 $\geq 23$ 的质因子的数,按照其最大质因子分组,一组一组的往里更新

注意到在处理第二种情况的数的时候,第一人不选择该组数字的情况和第二分不选择该组数字的情况重复了,均为 $f[s1][s2]$ ,所以需要去掉重复部分

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 510;
bool nop[N];
int pri[N], priCnt;

int bin[10];

int num[N], fac[N];

int priNum[510];

int n, p;

int f[1 << 8][1 << 8];
int g[2][1 << 8][1 << 8];

vector <int> other[510];
int maxNum;

void getPri() {
    for(int i = 2; i <= 500; ++ i) {
        if(!nop[i]) {
            pri[++ priCnt] = i;
            priNum[i] = priCnt;
        }
        for(int j = 1; j <= priCnt && i * pri[j] <= 500; ++ j) {
            nop[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}
void getFac() {
    bin[0] = 1;
    for(int i = 1; i <= 8; ++ i)
        bin[i] = bin[i - 1] << 1;
    for(int i = 2; i <= 500; ++ i) {
        num[i] = i;
        for(int j = 1; j <= 8; ++ j) {
            while(num[i] % pri[j] == 0) {
                fac[i] |= bin[j - 1];
                num[i] /= pri[j];
            }
        }
    }
}
int main() {
    getPri(); getFac();
    n = read(); p = read();
    f[0][0] = 1;
    for(int i = 2; i <= n; ++ i) {
        if(num[i] == 1) {
            for(int s1 = bin[8] - 1; s1 >= 0; -- s1) {
                for(int s2 = bin[8] - 1; s2 >= 0; -- s2) {
                    if(!(fac[i] & s2)) {
                        f[s1 | fac[i]][s2] += f[s1][s2];
                        if(f[s1 | fac[i]][s2] >= p) f[s1 | fac[i]][s2] -= p;
                    }
                    if(!(fac[i] & s1)) {
                        f[s1][s2 | fac[i]] += f[s1][s2];
                        if(f[s1][s2 | fac[i]] >= p) f[s1][s2 | fac[i]] -= p;
                    }
                }
            }
        }
        else {
            other[priNum[num[i]] - 8].push_back(i);
            maxNum = max(maxNum, priNum[num[i]] - 8);
        }
    }
    for(int i = 1; i <= maxNum; ++ i) {
        memcpy(g[0], f, sizeof(g[0]));
        memcpy(g[1], f, sizeof(g[1]));
        for(auto it : other[i]) {
            for(int s1 = bin[8] - 1; s1 >= 0; -- s1) {
                for(int s2 = bin[8] - 1; s2 >= 0; -- s2) {
                    if(!(fac[it] & s2)) {
                        g[0][s1 | fac[it]][s2] += g[0][s1][s2];
                        if(g[0][s1 | fac[it]][s2] >= p) g[0][s1 | fac[it]][s2] -= p;
                    }
                    if(!(fac[it] & s1)) {
                        g[1][s1][s2 | fac[it]] += g[1][s1][s2];
                        if(g[1][s1][s2 | fac[it]] >= p) g[1][s1][s2 | fac[it]] -= p;
                    }
                }
            }
        }
        for(int s1 = bin[8] - 1; s1 >= 0; -- s1)
            for(int s2 = bin[8] - 1; s2 >= 0; -- s2)
                f[s1][s2] = ((g[0][s1][s2] + g[1][s1][s2]) % p - f[s1][s2] + p) % p;
    }
    int ans = 0;
    for(int s1 = bin[8] - 1; s1 >= 0; -- s1)
        for(int s2 = bin[8] - 1; s2 >= 0; -- s2) {
            ans += f[s1][s2];
            if(ans >= p) ans -= p;
        }
    printf("%d\n", ans);
    return 0;
}
Comments

添加新评论