技术教程 2020牛客NOIP赛前集训营-提高组（第二场）- B.包含 （FWT） 正文

2020牛客NOIP赛前集训营-提高组（第二场）- B.包含 （FWT）

2022-10-15,,,,

题面

题解

这题就是个快速沃尔什变换的模板题，输入ai时，令s[ai]=1，对s[]做一遍DWT_AND(s)（快速沃尔什正变换，按位与），然后直接访问s[x]完事。

#include<map>

#include<queue>

#include<cmath>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 10000005

#define LL long long

#define DB double

#define ENDL putchar('\n')

#define lowbit(x) ((-x)&(x))

LL read() {

	LL f = 1,x = 0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f=-f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s=getchar();}

	return f*x;

}

const int MOD = 998244353;

const int N = 1048576;

int n,m,i,j,s,o,k;

bool a[N+5];

void DWT_AND(bool *s) {

	for(int k = 1;k < N;k <<= 1) {

		for(int i = 0;i < N;i += (k<<1)) {

			for(int j = i;j < i+k;j ++) {

				s[j] |= s[j+k];

			}

		}

	}

	return ;

}

int main() {

	n = read();m = read();

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

		s = read();

		a[s] = 1;

	}

	DWT_AND(a);

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

		s = read();

		printf(a[s] ? "yes\n":"no\n");

	}

	return 0;

}

2020牛客NOIP赛前集训营-提高组（第二场）- B.包含 （FWT）的相关教程结束。

《2020牛客NOIP赛前集训营-提高组（第二场）- B.包含 （FWT）.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!