UVALive - 6886 Golf Bot 多项式乘法（FFT）

题目链接：

http://acm.hust.edu.cn/vjudge/problem/129724

Golf Bot

Time Limit: 15000MS

题意

题解

多项式乘法,用快速傅里叶变化加速，时间复杂度：O(nlogn)。

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

const int maxn=555555;

int vis[maxn],n;

struct Complex {

	double real, image;

	Complex(double real, double image):real(real),image(image) {}

	Complex() {}

	friend Complex operator + (const Complex &c1, const Complex &c2) {

		return Complex(c1.real + c2.real, c1.image + c2.image);

	}

	friend Complex operator - (const Complex &c1, const Complex &c2) {

		return Complex(c1.real - c2.real, c1.image - c2.image);

	}

	friend Complex operator * (const Complex &c1, const Complex &c2) {

		return Complex(c1.real*c2.real - c1.image*c2.image, c1.real*c2.image + c1.image*c2.real);

	}

}a[maxn];

struct IterativeFFT {

	Complex A[maxn];

	int rev(int id, int len) {

		int ret = 0;

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

			ret <<= 1;

			if(id & (1 << i)) ret |= 1;

		}

		return ret;

	}

	//当DFT= 1时是DFT, DFT = -1则是逆DFT

	//对长度为len(2的幂)的数组进行DFT变换

	void FFT(Complex *a,int len, int DFT) {

		for(int i = 0; i < len; i++)

			A[rev(i, len)] = a[i];

		for(int s = 1; (1 << s) <= len; s++) {

			int m = (1 << s);

			Complex wm = Complex(cos(DFT*2*PI/m), sin(DFT*2*PI/m));

			//这一层结点的包含数组元素个数都是(1 << s)

			for(int k = 0; k < len; k += m) {

				Complex w = Complex(1, 0);

				//折半引理, 根据两个子节点计算父亲节点

				for(int j = 0; j < (m >> 1); j++) {

					Complex t = w*A[k + j + (m >> 1)];

					Complex u = A[k + j];

					A[k + j] = u + t;

					A[k + j + (m >> 1)] = u - t;

					w = w*wm;

				}

			}

		}

		if(DFT == -1) for(int i = 0; i < len; i++) A[i].real /= len, A[i].image /= len;

		for(int i=0; i<len; i++) a[i]=A[i];

	}

} myfft;

void init() {

	rep(i,0,maxn) a[i]=Complex(0,0);

	a[0].real=1;

	clr(vis,0);

}

int main() {

	while(scanf("%d",&n)==1&&n) {

		init();

		int ma=0;

		rep(i,0,n){

			int x;

			scanf("%d",&x);

			ma=max(ma,x);

			a[x].real=1.0;

		}

		int len=1;

		while(len<ma) len<<=1;

		len<<=1;

		myfft.FFT(a, len, 1);

		rep(i,0,len){

			a[i]=a[i]*a[i];

		}

		myfft.FFT(a,len,-1);

		rep(i,0,len){

			if(a[i].real>eps) vis[i]=1;

		}

		int q;

		scanf("%d",&q);

		int ans=0;

		while(q--) {

			int x;

			scanf("%d",&x);

			if(vis[x]) {

				ans++;

			}

		}

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

	}

	return 0;

}

这题用bitset也能做，不过跑的没有FFT快。

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=222223;

bitset<maxn> bset1,bset2;

int arr[maxn];

int n;

int main() {

    while(scanf("%d",&n)==1&&n){

    	bset1.reset();

    	rep(i,0,n){

    		scanf("%d",&arr[i]);

			bset1.set(arr[i]);

		}

		bset2=bset1;

		rep(i,0,n){

			bset1|=bset2<<arr[i];

		}

		int q; scanf("%d",&q);

		int ans=0;

		while(q--){

			int x; scanf("%d",&x);

			if(bset1.test(x)) ans++;

		}

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

	}

    return 0;

}

//end-----------------------------------------------------------------------