概要

比赛地址

2020 Multi-University Training Contest 7

1008. Heart

题目大意：

给 n 个法术，每种法术需要一个物品的集合，每个物品只能被使用一次；一个可同时使用的法术的集合的权值为各法术权值的乘积。
共 q 次询问，问恰好使用物品集合为 x 的所有法术集合的权值和。

解题思路：

如果规定每个物品集合至多有两个法术，就是裸的子集卷积了。暴力做 21 次全子集卷积一定会超时。考虑优化：

由于最高位相同的法术不可能同时存在，即不可能卷积在一起，我们把物品按照最高位分组再分别卷积起来。

复杂度分析：O\left(\sum_{i=1}^{n}i^2\cdot 2^i \right)=O\left(i^n\cdot 2^n \right)，且常数小于 2。

#include <bits/stdc++.h>
using namespace std;
#define pct(x) __builtin_popcount(x)
const int P = 998244353;

void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}
void sub(int &x, int y) {
    (x -= y) < 0 && (x += P);
}
void FWTor(vector<int> &a, bool rev) {
    int n = (int)a.size();
    for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
        for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
            if (!rev) add(a[i + j + m], a[i + j]);
            else sub(a[i + j + m], a[i + j]);
        }
    }
}

vector<int> Subset(vector<int> &a1, vector<int> &a2, int lim) {
    int n = 1 << lim;
    vector<int> ret(n);
    vector< vector<int> > a(lim + 1, vector<int>(n)), b = a, A = a;
    for (int i = 0; i < n; i++) {
        a[pct(i)][i] = a1[i]; b[pct(i)][i] = a2[i];
    }
    for (int i = 0; i <= lim; i++) {
        FWTor(a[i], false); FWTor(b[i], false);
    }
    for (int i = 0; i <= lim; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k < n; k++) {
                (A[i][k] += 1LL * a[j][k] * b[i - j][k] % P) %= P;
            }
        }
    }
    for (int i = 0; i <= lim; i++) FWTor(A[i], true);
    for (int i = 0; i < n; i++) ret[i] = A[pct(i)][i];
    return ret;
}
vector<int> conv(vector<int> &a) {
    int Base = 21, Len = 1 << Base;
    vector<int> ret(Len); ret[0] = 1;
    for (int n = 0; n < Base; n++) {
        int ful = 1 << n;
        auto A = vector<int>(ret.begin(), ret.begin() + ful);
        auto B = vector<int>(a.begin() + ful, a.begin() + ful * 2);
        auto C = Subset(A, B, n);
        for (int i = ful; i < ful * 2; i++) {
            ret[i] = C[i - ful];
        }
    }
    return ret;
}

int n, m;

int main(int argc, const char * argv[]) {
    scanf("%d", &n); int lim = 21;
    vector<int> a(1 << lim), ans;
    for (int i = 1, p, b; i <= n; i++) {
        scanf("%d%d", &p, &b);
        (a[b] += p) %= P;
    }
    ans = conv(a);
    scanf("%d", &m);
    for (int i = 1, x; i <= m; i++) {
        scanf("%d", &x);
        printf("%d\n", ans[x]);
    }
    return 0;
}