欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ4589: Hard Nim(FWT 快速幂)

程序员文章站 2022-04-14 20:20:45
题意 "题目链接" Sol 神仙题Orzzzz 题目可以转化为从$\leqslant M$的质数中选出$N$个$xor$和为$0$的方案数 这样就好做多了 设$f(x) = [x \text{是质数}]$ $n$次异或FWT即可 快速幂优化一下,中间不用IFWT,最后转一次就行(~~然而并不知道为什 ......

题意

题目链接

sol

神仙题orzzzz

题目可以转化为从\(\leqslant m\)的质数中选出\(n\)\(xor\)和为\(0\)的方案数

这样就好做多了

\(f(x) = [x \text{是质数}]\)

\(n\)次异或fwt即可

快速幂优化一下,中间不用ifwt,最后转一次就行(然而并不知道为什么)

哪位大佬教教我这题的dp怎么写呀qwqqqq

死过不过去样例。。

#include<bits/stdc++.h>
using namespace std;
const int maxn = (1 << 17) + 10, mod = 998244353, inv2 = 499122177;
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], b[maxn], c[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 fwtor(int *a, int opt) {
    for(int mid = 1; mid < n; mid <<= 1) 
        for(int r = mid << 1, j = 0; j < n; j += r)
            for(int k = 0; k < mid; k++) 
                if(opt == 1) a[j + k + mid] = add(a[j + k], a[j + k + mid]);
                else a[j + k + mid] = add(a[j + k + mid], -a[j + k]);
}
void fwtand(int *a, int opt) {
    for(int mid = 1; mid < n; mid <<= 1) 
        for(int r = mid << 1, j = 0; j < n; j += r)
            for(int k = 0; k < mid; k++) 
                if(opt == 1) a[j + k] = add(a[j + k], a[j + k + mid]);
                else a[j + k] = add(a[j + k], -a[j + k + mid]);
}
void fwtxor(int *a, int opt) {
    for(int mid = 1; mid < n; mid <<= 1) 
        for(int r = mid << 1, j = 0; j < n; 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 = 1 << (read());
    for(int i = 0; i < n; i++) a[i] = read();
    for(int i = 0; i < n; i++) b[i] = read();
    fwtor(a, 1); fwtor(b, 1);
    for(int i = 0; i < n; i++) c[i] = mul(a[i], b[i]);
    fwtor(c, -1); fwtor(a, -1); fwtor(b, -1);
    for(int i = 0; i < n; i++) printf("%d ", c[i]); puts("");
    fwtand(a, 1); fwtand(b, 1);
    for(int i = 0; i < n; i++) c[i] = mul(a[i], b[i]);
    fwtand(c, -1); fwtand(a, -1); fwtand(b, -1);    
    for(int i = 0; i < n; i++) printf("%d ", c[i]); puts("");
    fwtxor(a, 1); fwtxor(b, 1);
    for(int i = 0; i < n; i++) c[i] = mul(a[i], b[i]);
    fwtxor(c, -1); fwtxor(a, -1); fwtxor(b, -1);    
    for(int i = 0; i < n; i++) printf("%d ", c[i]);
    return 0;
}