专栏首页数据结构与算法UOJ#310. 【UNR #2】黎明前的巧克力(FWT)

UOJ#310. 【UNR #2】黎明前的巧克力(FWT)

题意

题目链接

Sol

挂一个讲的看起来比较好的链接

然鹅我最后一步还是没看懂qwq。。

坐等SovietPower大佬发博客

#include<bits/stdc++.h>
using namespace std;
const int MAXN = (1 << 23) + 10, mod = 998244353, inv2 = (mod + 1) / 2, inv4 = 748683265, lim = 1048576;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, a[MAXN], po3[MAXN];
int add(int x, int y) {
    if(x + y < 0) return x + y + mod;
    return x + y >= mod ? x + y - mod : x + y;
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}
void FWT(int *a, int opt) {
    for(int mid = 1; mid < lim; mid <<= 1) 
        for(int R = mid << 1, j = 0; j < lim; j += R)
            for(int k = 0; k < mid; k++) {
                int x = a[j + k], y = a[j + k + mid];
                if(opt == 1) a[j + k] = add(x, y), a[j + k + mid] = add(x, -y);
                else a[j + k] = mul(add(x, y), inv2), a[j + k + mid] = mul(add(x, -y), inv2);               
            }
}
int main() {
    N = read();
    for(int i = 1; i <= N; i++) a[read()]++;
    FWT(a, 1);
    po3[0] = 1;
    for(int i = 1; i <= N; i++) po3[i] = mul(3, po3[i - 1]);
    for(int i = 0; i < lim; i++) {
        a[i] = add(mul(2, a[i]), N);
        int c3 = mul(add(a[i], N), inv4);
        a[i] = po3[c3];
        if((N - c3) & 1) a[i] = mod - a[i];
    }
    FWT(a, -1);
    cout << (a[0] - 1 + mod) % mod;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ3453: tyvj 1858 XLkxc(拉格朗日插值)

    \[\sum_{i = 0} ^n \sum_{j = 1}^{a + id} \sum_{x =1}^j x^k \pmod P\]

    attack
  • BZOJ3262: 陌上花开(cdq分治)

    第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。

    attack
  • 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

    那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列,显然这个序列要满足最后一个\(\mid 1\)要在\(\& 0\)之后

    attack
  • BZOJ3262: 陌上花开(cdq分治)

    第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。

    attack
  • BZOJ3453: tyvj 1858 XLkxc(拉格朗日插值)

    \[\sum_{i = 0} ^n \sum_{j = 1}^{a + id} \sum_{x =1}^j x^k \pmod P\]

    attack
  • 洛谷P2762 太空飞行计划问题(最大权闭合图)

    attack
  • 2018年第九届蓝桥杯B组题解

    按着题目把这些数转换成8字节的二进制数就可以了,负数的二进制是补码。可以自己写个函数实现一下,实际效果图:

    Ch_Zaqdt
  • HDU 1875 畅通工程再续(kruskal)

    畅通工程再续 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

    ShenduCC
  • poj 1562 dfs

    瑾诺学长
  • 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

    那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列,显然这个序列要满足最后一个\(\mid 1\)要在\(\& 0\)之后

    attack

扫码关注云+社区

领取腾讯云代金券