LibreOJ 2257 「SNOI2017」遗失的答案

发表于 | 分类于 | 7

看到 GCD / LCM，果断莫反（雾
但是发现莫反并没有办法处理强制选 X 的情况……

换个方向。
值域 108，所以 L 最多有 8 个质因子。
所以考虑状压 DP。

根据数论套路，令 N←⌊NG⌋,L←LG。当然，若 G∤L 直接无解。

那么问题变为在 1…N 内选若干个互质的正整数，强制选择 X，使得它们的 LCM 为 L 的方案数。
也即这些数的每个质因子的指数的最小值为 0，最大值为 L 对应的指数。

考虑如此状压一个数：前一半表示这个数每个质因子指数是否为 0，后一半表示这个数每个质因子指数是否等于 L 对应的指数。
将 1…N 内 L 的约数拿出来，按照状态分组，发现合法的状态并不多。
设 f0/1,i,j 表示考虑了第 i 种状态之前 / 之后所有状态，总状态为 j 的方案数。
选择一种状态的贡献是这种状态对应的整数的子集个数。

强制选择一个 X 即合并 f0,i 和 f1,i，其中 i 为 X 的状态，这个可以 FWT 合并。
注意此时第 i 种状态的贡献要考虑强制选择了至少一个数。

又是一道在洛谷不开 O2 跑不过的题（

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <cstdio>
#include <vector>
#include <algorithm>
#define add(x,y) (x + y >= mod ? x + y - mod : x + y)
#define dec(x,y) (x < y ? x - y + mod : x - y)
using namespace std;
const int C = 8;
const int N = 16;
const int S = 1 << N;
const int CNT = 700;
const int mod = 1e9 + 7;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int n,g,l,q,s;
inline void fwt(int *a,int type,int n)
{
    for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
        for(register int i = 0;i < n;i += w)
            for(register int j = 0;j < m;++j)
                a[i | j | m] = type == 1 ? add(a[i | j | m],a[i | j]) : dec(a[i | j | m],a[i | j]);
}
struct Factor
{
    int fac[C + 5],e[C + 5],cnt;
    inline Factor(int n = 1)
    {
        cnt = 0;
        for(register int i = 2;i * i <= n;++i)
        {
            !(n % i) && (fac[++cnt] = i,e[cnt] = 0);
            for(;!(n % i);n /= i,++e[cnt]);
        }
        n > 1 && (fac[++cnt] = n,e[cnt] = 1);
        fac[cnt + 1] = 0x3f3f3f3f;
    }
} L;
inline int state(int n)
{
    Factor f(n);
    int s = (1 << L.cnt) - 1;
    for(register int i = 1,j;i <= f.cnt;++i)
        j = lower_bound(L.fac + 1,L.fac + L.cnt + 1,f.fac[i]) - L.fac,
        s &= ~(1 << j - 1),s |= ((f.e[i] == L.e[j]) << L.cnt + j - 1);
    return s;
}
int w[CNT + 5],cnt,c[S + 5],val[CNT + 5];
int f[2][CNT + 5][S + 5],ans[CNT + 5];
int main()
{
    scanf("%d%d%d%d",&n,&g,&l,&q);
    if(l % g)
    {
        for(;q;--q)
            puts("0");
        return 0;
    }
    n /= g,l /= g,L = Factor(l),s = 1 << 2 * L.cnt;
    for(register int i = 1;i <= n;++i)
        !(l % i) && ++c[state(i)];
    for(register int i = 0;i < s;++i)
        c[i] && (w[++cnt] = i,val[cnt] = (fpow(2,c[i]) + mod - 1) % mod);
    f[0][1][0] = f[1][cnt][0] = 1;
    for(register int i = 1;i < cnt;++i)
        for(register int j = 0;j < s;++j)
            f[0][i + 1][j] = add(f[0][i + 1][j],f[0][i][j]),
            f[0][i + 1][j | w[i]] = (f[0][i + 1][j | w[i]] + (long long)f[0][i][j] * val[i]) % mod;
    for(register int i = cnt;i > 1;--i)
        for(register int j = 0;j < s;++j)
            f[1][i - 1][j] = add(f[1][i - 1][j],f[1][i][j]),
            f[1][i - 1][j | w[i]] = (f[1][i - 1][j | w[i]] + (long long)f[1][i][j] * val[i]) % mod;
    for(register int i = 1;i <= cnt;++i)
    {
        fwt(f[0][i],1,s),fwt(f[1][i],1,s);
        for(register int j = 0;j < s;++j)
            f[0][i][j] = (long long)f[0][i][j] * f[1][i][j] % mod;
        fwt(f[0][i],-1,s);
        for(register int j = 0;j < s;++j)
            if((j | w[i]) == s - 1)
                ans[i] = add(ans[i],f[0][i][j]);
        ans[i] = (long long)ans[i] * fpow(2,c[w[i]] - 1) % mod;
    }
    for(int x;q;--q)
    {
        scanf("%d",&x);
        if(x % g)
        {
            puts("0");
            continue;
        }
        x /= g;
        if(l % x || x > n)
        {
            puts("0");
            continue;
        }
        printf("%d\n",ans[lower_bound(w + 1,w + cnt + 1,state(x)) - w]);
    }
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment