Tag-FFT

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-07-02 10:25:10 |  0 Comments  |  FFT

BZOJ 3527 [ZJOI2014]力

题解

就是把qj除掉,然后可以发现是裸的两个卷积形式,直接上FFT就可以。

这个博客写的非常好,我个人就比较渣了QAQ https://blog.csdn.net/qq_33929112/article/details/54590319

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const int maxn = (1<<18) + 5;
const int INF = 1e9;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = (num << 1) + (num << 3) + c - '0';
	return (flag ? -1 : 1) * num;
}
struct comp{
	double x,y;
	comp(double a = 0,double b = 0):x(a),y(b){};
};
comp operator + (comp a,comp b){return comp(a.x + b.x,a.y + b.y);}
comp operator - (comp a,comp b){return comp(a.x - b.x,a.y - b.y);}
comp operator * (comp a,comp b){return comp(a.x*b.x - a.y * b.y,a.x * b.y + a.y * b.x);}
comp conj(comp a){
	return comp(a.x,-a.y);
}
struct FFT{
	int n,rev[maxn];
	void get_inv(int bit){
		n = 1;int k = 0;
        while(n < bit) n <<= 1,k++;
        
 2017-04-01 10:00:46 |  0 Comments  |  FFT

FFT模板 【UOJ】模板题库 多项式乘法

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <complex>
using namespace std;
const int maxn = 3e5+5;
const double pi = acos(-1);
int n = 0;
int n1,n2;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = num * 10 + c - '0';
	return (flag ? -1 : 1) * num;
}
struct FFT{
	complex<double>omega[maxn],iomega[maxn];
	void init(const int n){
		for(int i = 0;i < n;++i){
			omega[i] = complex<double>(cos(2*pi*i/n),sin(2*pi*i/n));
			iomega[i] = conj(omega[i]);
		}
	}
	void trans(complex<double> *a,const int n,const complex<double> *omega){
		int k = 0;
		while((1 << k) < n)k++;
		for(int i = 0;i < n;++i){
			int t = 0;
			for(int j = 0;j < k;j++)if(i&(1 << j))t |= (1 << (k-j-1));
			if(i < t)swap(a[i],a[t]);
		}
		for(int l = 2;l <= n;l *= 2){
			int m = l / 2;
			for(co
Title - Artist
0:00