「SNOI2017」遗失的答案

发表于 分类于

题目链接：https://loj.ac/problem/2257。

可以一开始令$L=L/G$，显然$G\not \mid L$的时候答案全是$0$，那么现在只需要考虑$L$的约数即可。

对于每个$L$的质因数，考虑选出来的数的当前质因数的指数，显然要满足最小值为$0$，最大值等于$L$的指数。

注意到$L$的质因数最多$8$个，并且约数个数不超过$1000$个，我们可以状压$\rm dp$：设$f_{i,s,t}$表示考虑了前$i$个约数，有$s$这些质因数达到了最小值，$t$达到了最大值。

由于我们现在有一个限制条件是说必须选$x$这个数，所以我们在搞出一个$g$表示后缀的$\rm dp$值，那么每次把$f_{i-1},g_{i+1}$合并一下就可以得到需要的$\rm dp$值。

注意到这是个或卷积，可以$\rm FWT$优化。

假设当前卷积出来的东西是$h_s$，那么答案就是$\sum _{t\mid state_x=all}h_t$，利用$\rm FWT​$做一遍超集和就好了。（我写完了才发现这地方直接暴力预处理就好了。。。不需要这么花里胡哨。。我亏了）

复杂度很玄学。。预处理看起来像$2^{16}\cdot 16\cdot 1000$，但是实际上没有数可以卡慢，因为质因数达到最大值之后约数个数就不多了，反之也是一样的。

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
104
105
106
107
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int n,G,l,f[1002][(1<<16)+1],g[1002][(1<<16)+1],h[1002][(1<<16)+1],q,r[maxn],cnt,pri[maxn],tot,ms[maxn];

void gen() {
    for(int i=1;i*i<=l;i++) {
        if(l%i) continue;
        r[++cnt]=i;
        if(i*i!=l) r[++cnt]=l/i;
    }sort(r+1,r+cnt+1);
    int x=l;
    for(int i=2;i*i<=x;i++) {
        if(x%i) continue;
        pri[++tot]=i;
        while(x%i==0) x/=i;
    }if(x!=1) pri[++tot]=x;
    for(int i=1;i<=cnt;i++) {
        for(int j=1;j<=tot;j++) {
            if(r[i]%pri[j]) ms[i]|=1<<(j-1);
            if((l/r[i])%pri[j]) ms[i]|=1<<(j+tot-1);
        }
    }
    while(r[cnt]*G>n) cnt--;
}

void update(int &x,int y) {x+=y;if(x>=mod) x-=mod;}

void fwt_or(int *r,int op) {
    int N=1<<(tot*2);
    for(int i=1;i<N;i<<=1)
        for(int j=0;j<N;j+=i<<1)
            for(int k=0;k<i;k++)
                if(op>0) update(r[i+j+k],r[j+k]);
                else r[i+j+k]=(r[i+j+k]-r[j+k]+mod)%mod;
}

void fwt_and(int *r,int op) {
    int N=1<<(tot*2);
    for(int i=1;i<N;i<<=1)
        for(int j=0;j<N;j+=i<<1)
            for(int k=0;k<i;k++)
                if(op>0) update(r[j+k],r[i+j+k]);
                else r[j+k]=(r[j+k]-r[i+j+k]+mod)%mod;
}

int main() {
    read(n),read(G),read(l),read(q);
    if(l%G) {for(int i=1;i<=q;i++) puts("0");return 0;}
    l/=G;gen();
    f[0][0]=g[cnt+1][0]=1;
    for(int i=0;i<cnt;i++)
        for(int s=0;s<1<<(tot*2);s++) {
            update(f[i+1][s],f[i][s]);
            update(f[i+1][s|ms[i+1]],f[i][s]);
        }
    for(int i=cnt+1;i>1;i--)
        for(int s=0;s<1<<(tot*2);s++) {
            update(g[i-1][s],g[i][s]);
            update(g[i-1][s|ms[i-1]],g[i][s]);
        }
    for(int i=1;i<=cnt;i++) {
        fwt_or(f[i-1],1),fwt_or(g[i+1],1);
        for(int s=0;s<1<<(tot*2);s++) h[i][s]=1ll*f[i-1][s]*g[i+1][s]%mod;
        fwt_or(h[i],-1);
        fwt_and(h[i],1);
    }
    for(int i=1;i<=q;i++) {
        int x;read(x);
        if(x%G) {puts("0");continue;}
        x/=G;
        if(l%x||x>n) {puts("0");continue;}
        int p=lower_bound(r+1,r+cnt+1,x)-r;
        write(h[p][(1<<(tot*2))-1-ms[p]]);
    }
    return 0;
}