浏览器

结论popcnt(x^y)和popcnt(x)+popcnt(y)的奇偶性相同。

然后就是popcnt为奇数的乘为偶数的。预处理一下\(2^{16}\)次方以内的popcnt，直接\(O(1)\)算就行。

大师

就是求有多少个等差子序列。

方程很好写，\(f[i]\)表示以\(i\)结尾的等差子序列个数，\(f[i] = \sum_{j=1}^i f[j]*[a[i]-a[j]=d]\)，枚举一下公差就行了。这里要注意公差可能有正有负，不要一起枚举（我就在这错的）

#include <algorithm>

#include <cstdio>

#include <cstring>

typedef long long ll;

const int N = 1010;

const ll ha = 998244353;

const int M = 40010;

ll s[M], f[N], a[N], n, ans, mx;

void calc(ll d) {

    memset(s, 0, sizeof s);

    for (int i = 1; i <= n; ++i) {

        f[i] = (1 + s[a[i]]) % ha;

        if (a[i] + d >= 0 && a[i] + d <= mx) (s[a[i] + d] += f[i]) %= ha;

        (ans += f[i]) %= ha;

    }

}

int main() {

    n = read();

    for (int i = 1; i <= n; ++i) a[i] = read(), mx = std::max(mx, a[i]);

    for (int i = -mx; i <= mx; ++i) {

        calc(i);

    }

    ans = ans - mx * 2 * n % ha + ha;

    ans %= ha;

    printf("%lld\n", ans);

    return 0;

}

礼物

冲突就是一个子集关系。而子集关系又是偏序的。“偏序集最小反链覆盖等于最长链”。所以建一个子集关系的DAG跑一个最长路就行了。然后就是有一个虚点的技巧，每个集合只与比它少一个元素的集合连边，这样点数是\(O(2^k)\)的，边数是\(O(k2^k)\)的。跑最长路的时候真点是\(1\)虚点是\(0\)就行了。

#include <algorithm>

#include <cstdio>

const int N = (1 << 21);

const int M = N * 21;

int hd[N], to[M], nxt[M], w[N], cnt;

int f[N], rd[N], rn[N], tot[N];

int n, k, a[N];

inline void adde(int x, int y) {

    cnt++;

    to[cnt] = y;

    nxt[cnt] = hd[x];

    hd[x] = cnt;

}

int main() {

    n = read();

    k = read();

    for (int i = 1; i <= n; ++i) {

        a[i] = read();

        w[a[i]] = f[a[i]] = 1;

    }

    for (int i = (1 << k) - 1; i >= 0; --i) {

        for (int j = 0; j <= k; ++j)

            if (i >> j & 1) {

                adde(i, i ^ (1 << j));

            }

    }

    int ans = 0;

    for (int i = (1 << k) - 1; i >= 0; --i) {

        for (int j = hd[i]; j; j = nxt[j]) {

            f[to[j]] = std::max(f[to[j]], f[i] + w[to[j]]);

        }

        ans = std::max(ans, f[i]);

    }

    puts("1");

    printf("%d\n", ans);

    for (int i = 1; i <= n; ++i) {

        rn[i] = rd[f[a[i]]];

        rd[f[a[i]]] = i;

        tot[f[a[i]]]++;

    }

    for (int i = 1; i <= ans; ++i) {

        printf("%d ", tot[i]);

        for (int j = rd[i]; j; j = rn[j]) printf("%d ", a[j]);

        puts("");

    }

    return 0;

}

口袋里的纸飞机

咕。

巴特西

[LGR-054]洛谷10月月赛II

浏览器

大师

礼物

口袋里的纸飞机

最新文章

热门文章