题解 P5366 【[SNOI2017]遗失的答案】

· · 题解

滋磁去我的博客看啊

妙妙题..

首先判掉L不是G的倍数的情况.

然后先来考虑一下没有一定要包含X的这个限制的情况:

对于L的每个质因子p_i,设\text{MxP}(p_i,x)=k(p_i^k\mid x,p_i^{k+1}\not\mid x);

设m为L不同的质因子的个数.

我就是要选出来一些数使得对于每个质因子p_i,至少存在一个数x使得\text{MxP}(p_i,x)=\text{MxP}(p_i,L), 至少存在一个数y使得\text{MxP}(p_i,x)=\text{MxP}(p_i,G).

那么我们把每个数都看成一个长为2m的01串,记录它对于每一个质因子p_i,是否满足\text{MxP}(p_i,x)=\text{MxP}(p_i,L), 或满足\text{MxP}(p_i,x)=\text{MxP}(p_i,G).

那么我们最后就是要找若干个数使得它们或出来是一个长为2m的全是1的串.因为m \le 8,这道题就变得可做多了.

然后这个是可以\text{FWT}的.对于X的限制,记一个前后缀\text{FWT}的结果就好了,但是复杂度不太对.

我们可以考虑容斥:

我就是要求找出来一些数使它们或为全集,设:f(S)表示或出来为S的方案数,

g(S)=\sum_{T\subseteq S}f(T)

那么g(S)=2^{con(S)}(con(S)为S的子集的个数).然后这个就可以直接子集反演了:

f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T)

再考虑一下有X的限制.就是我们或出来的只能是X的超集.设f(S)表示或出来的数为S并且一定选中了X的方案数.这里的g(S)和上述的含义一样.只是g(S)=[X\subseteq S]2^{con(S)-1}.减一就是我们去掉没选X的这种情况.然后容斥和上面是一样的.

虽然询问有很多但是不同的01状态只有2^{2m},并且我们每次容斥时只用枚举X的超集就好了,所以复杂度为O(3^{2m}).(m\le 8)

代码:

/*
 * 2257.cpp
 * This file is part of 2257
 *
 * Copyright (C) 2019 - ViXbob
 *
 * 2257 is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * 2257 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with 2257. If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * There is no end though there is a start in space. ---Infinity.
 * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
 * Only the person who was wisdom can read the most foolish one from the history.
 * The fish that lives in the sea doesn't know the world in the land.
 * It also ruins and goes if they have wisdom.
 * It is funnier that man exceeds the speed of light than fish start living in the land.
 * It can be said that this is an final ultimatum from the god to the people who can fight.
 *
 * Steins;Gate
 */
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 1e9 + 7;
const int inf = 0x3f3f3f3f;

int n, G, L, Q, x, pow2[maxn], U, l[maxn], r[maxn], siz[maxn], N, ans[1 << 17];
vector<pair<int, int> > facL, data;

inline int read() {
    char ch = getchar(); int u = 0, f = 1;
    while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
    while(isdigit(ch))  { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }

inline void GetFac(int x, vector<pair<int, int> > &fac) {
    for(int i = 2; i * i <= x; i++) if(x % i == 0) {
        int cnt = 0;
        while(x % i == 0) x /= i, cnt++;
        fac.pb(mp(i, cnt));
    }
    if(x != 1) fac.pb(mp(x, 1));
}

inline void Binout(int S) {
    stack<int> st;
    while(S) st.push(S & 1), S >>= 1;
    rep(i, 1, N - st.size()) putchar('0');
    while(st.size()) putchar(st.top() + '0'), st.pop();
    putchar('\n');
}

inline pair<int, int> GetState(int x) {
    int S = 0, y = x;
//  cerr << "------------------------" << endl;
//  cerr << "x = " << x << endl;
    rep(i, 0, SIZE(facL) - 1) {
        int cnt = 0;
        while(x % facL[i].first == 0) x /= facL[i].first, cnt++;
        S |= (cnt == l[i]) << i;
        S |= (cnt == r[i]) << i + SIZE(facL);
    }
//  Binout(S);
    return mp(y, S);
}

inline void PreSolve() {
    GetFac(L, facL);
    pow2[0] = 1; N = SIZE(facL) << 1; U = (1 << N) - 1;
    rep(i, 1, U) pow2[i] = pls(pow2[i - 1], pow2[i - 1]);
    rep(i, 0, SIZE(facL) - 1) {
        r[i] = facL[i].second;
        int x = G;
        while(x % facL[i].first == 0) l[i]++, x /= facL[i].first;
    }
//  rep(i, 0, SIZE(facL) - 1) cerr << "l[" << i << "] = " << l[i] << ", r[" << i << "] = " << r[i] << endl;
    for(int i = 1; 1ll * i * i <= L; i++) if(L % i == 0) {
        if(i % G == 0 && i <= n) data.pb(GetState(i));
        if(i * i != L && (L / i) % G == 0 && (L / i) <= n) data.pb(GetState(L / i));
    }
    sort(data.begin(), data.end());
    for(auto v : data) siz[v.second]++;
    rep(i, 0, N - 1) rep(S, 0, U) if(S >> i & 1) siz[S] += siz[S ^ (1 << i)];
//  rep(S, 0, U) cerr << "size[" << S << "] = " << siz[S] << endl;
}

inline int Solve(int x, int rnt = 0) {
    auto it = *lower_bound(data.begin(), data.end(), mp(x, 0));
    if(ans[it.second] != -1) return ans[it.second];
    int T = it.second, S = U ^ T; rnt = __builtin_popcount(T) & 1 ? dec(rnt, pow2[siz[T] - 1]) : pow2[siz[T] - 1];
    for(int S1 = S; S1; S1 = (S1 - 1) & S) 
        if(__builtin_popcount(S1 | T) & 1) rnt = dec(rnt, pow2[siz[S1 | T] - 1]);
        else rnt = pls(rnt, pow2[siz[S1 | T] - 1]);
    return ans[it.second] = rnt;
}

int main() {
//  freopen("1.in", "r", stdin);
//  freopen("my.out", "w", stdout);
    n = read(); G = read(); L = read(); Q = read();
    if(L % G) { rep(i, 1, Q) puts("0"); return 0; }
    PreSolve();
    memset(ans, -1, sizeof(ans));
    rep(i, 1, Q) {
        x = read();
        if(x % G != 0 || L % x != 0 || x > n) puts("0");
        else printf("%d\n", Solve(x));
    }
    return 0;
}
/*
2 * 3 * 5
1 2 3 4 5
1
2
2
0
2
*/