【题解】LOJ 2257 「SNOI2017」遗失的答案

请注意,本文编写于 97 天前,最后修改于 97 天前,其中某些信息可能已经过时。

Problem

有 $n$ 个物品,编号为 $1-n$

问使得物品编号最大公约数为 $G$ ,最小公倍数为 $L$ 的集合中有多少个包含了物品 $X$

Thought

首先我们将所有数先除掉最小公倍数,问题转化为:

编号在 $[1,\frac{n}{L}]$ 范围内的物品,取一个集合使得最大公约数为 $1$ ,最小公倍数为 $\frac{G}{L}$ ,有多少个这样的集合包含了编号为 $\frac{X}{L}$ 的物品

那么将 $\frac{G}{L}$ 质因数分解,发现次数最高为 $26$ ,最多 $8$ 个不同质数,为 $p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$ 的形式

其限制转化为集合内对于每个质数 $p_x$ 至少出现一个次数为 $0$ 的,至少出现一个次数为 $c_x$ 的,其他的均在 $[0,c_x]$ 范围内

考虑算出所有的在范围内的数,并且将每个数是否卡到上/下界存下来,发现这样的数不超过 $600$ 个

然后直接 $FWT$ 跑出前缀和后缀,然后每个位置不选的情况
最终每个位置的答案为该位置对应的卡上下界情况异或的超集

至于求超集就直接很简单啦,分治就完事了

由于比较卡常,所以手动做做 $FWT$ 会快一点...

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read() {
    ll ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int n, g, l, q;
int flag;

const int PRI = 10010;
const int mod = 1000000007;

bool no[PRI];
int pri[PRI], priCnt;

int UP[10];
int DOWN[10];
int upper[10];
int lower[10];
int bas[10];
int num;

int sta[770], top;
int match[770];

int pre[770][1 << 16];
int suf[770][1 << 16];
int mer[1 << 16];

int N;

bool vis[100000010];
int Ans[100000010];

void prepare() {
    for(int i = 2; i < PRI; ++ i) {
        if(!no[i])
            pri[++ priCnt] = i;
        for(int j = 1; j <= priCnt && i * pri[j] < PRI; ++ j) {
            no[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}

bool work(int down, int up) {
    for(int i = 1; i <= priCnt; ++ i) {
        if(up % pri[i] == 0) {
            ++ num;
            bas[num] = pri[i];
            while(up % pri[i] == 0) {
                ++ upper[num];
                up /= pri[i];
            }
            while(down % pri[i] == 0) {
                ++ lower[num];
                down /= pri[i];
            }
            if(upper[num] < lower[num])
                return 1;
        }
    }
    if(up != 1) {
        ++ num;
        bas[num] = up;
        upper[num] = 1;
        while(down % up == 0) {
            ++ lower[num];
            down /= up;
        }
        if(upper[num] < lower[num])
            return 1;
    }
    N = 1 << (num * 2);
    if(down != 1) return 1;
    return 0;
}

void work_false() {
    q = read();
    while(q --)
        puts("0");
}

void dfs(int x, ll now) {
    if(x > num) {
        vis[now] = 1;
        sta[++ top] = now;
    }
    else
        for(int i = 0; i <= upper[x] && now <= n; ++ i, now *= bas[x]) {
            if(i >= lower[x])
                dfs(x + 1, now);
        }
}

int M(int x) {
    while(x < 0) x += mod;
    while(x >= mod) x -= mod;
    return x;
}

void FWT_OR(int *a, int n, int f) {
    for(int i = 1; i < n; i <<= 1)
        for(int j = 0; j < n; j += (i << 1))
            for(int k = 0; k < i; ++ k) {
                int x = a[j + k], y = a[i + j + k];
                a[i + j + k] = M(f * x + y);
            }
}

void FWT_AND(int *a, int n, int f) {
    for(int i = 1; i < n; i <<= 1)
        for(int j = 0; j < n; j += (i << 1))
            for(int k = 0; k < i; ++ k) {
                int x = a[j + k], y = a[i + j + k];
                a[j + k] = M(x + f * y);
            }
}

void FWT_OR_HAND(int *a, int n, int num) {
    for(int i = 0; i < n; ++ i)
        if((i & num )== num)
            ++ a[i];
}

void work_true() {
    dfs(1, 1);
    sort(sta + 1, sta + top + 1);
    for(int i = 1; i <= top; ++ i) {
        int now = sta[i];
        for(int j = 1; j <= num; ++ j) {
            int Exp = 0;
            while(now % bas[j] == 0) {
                now /= bas[j];
                ++ Exp;
            }
            if(Exp == lower[j])
                match[i] |= (1 << (j - 1));
            if(Exp == upper[j])
                match[i] |= (1 << (j - 1 + num));
        }
        FWT_OR_HAND(pre[i], N, 0);
        FWT_OR_HAND(suf[i], N, 0);
        
        FWT_OR_HAND(pre[i], N, match[i]);
        FWT_OR_HAND(suf[i], N, match[i]);
    }
    FWT_OR_HAND(pre[0], N, 0);
    FWT_OR_HAND(suf[top + 1], N, 0);
    for(int i = 1; i <= top; ++ i)
        for(int j = 0; j < N; ++ j)
            pre[i][j] = 1ll * pre[i - 1][j] * pre[i][j] % mod;
    for(int i = top; i >= 1; -- i)
        for(int j = 0; j < N; ++ j)
            suf[i][j] = 1ll * suf[i + 1][j] * suf[i][j] % mod;
    for(int i = 1; i <= top; ++ i) {
        for(int j = 0; j < N; ++ j)
            mer[j] = 1ll * pre[i - 1][j] * suf[i + 1][j] % mod;
        FWT_OR(mer, N, - 1);
        FWT_AND(mer, N, 1);
        Ans[sta[i]] = mer[(1 << (num * 2)) - 1 - match[i]];
    }
    q = read();
    while(q --)
        printf("%d\n", Ans[read()]);
}

int main() {
    prepare();
    n = read(); g = read(); l = read();
    flag = work(g, l);
    if(flag)
        work_false();
    else
        work_true();
    return 0;
}
Comments

添加新评论