石家庄住房和城乡建设局官方网站,西安做网站设计的公司,做电商网站有什语言好,三线城市做网站需求https://ac.nowcoder.com/acm/contest/11166/H 官方题解。
比赛时#xff0c;我们都是用暴力写的#xff0c;数据太弱了#xff0c;今天突然想起来#xff0c;用fft写了一下。
主要使用fft求差值的卷#xff0c;乘法我们在多项式的系数上做#xff0c;加减法 我们在多项…https://ac.nowcoder.com/acm/contest/11166/H 官方题解。
比赛时我们都是用暴力写的数据太弱了今天突然想起来用fft写了一下。
主要使用fft求差值的卷乘法我们在多项式的系数上做加减法 我们在多项式的指数上做。
做减法的时候我们把负数加N变成正数即可。
下面是代码
#include cstdio
#include cstring
#include string
#include cmath
#include iostream
#include algorithm
#include queue
#include cstdlib
#include stack
#include vector
#include set
#include map
#include bitset
#include complex
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define sc secondusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairll,ll pii;
const ll mod1e97;
const ll N 2e610;
const double eps 1e-6;
const double PIacos(-1);
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
int dx[8] {1,0,-1,0,1,1,-1,-1}, dy[8] {0,1,0,-1,1,-1,1,-1};
struct Complex
{double x, y;Complex operator (const Complex t) const{return {x t.x, y t.y};}Complex operator- (const Complex t) const{return {x - t.x, y - t.y};}Complex operator* (const Complex t) const{return {x * t.x - y * t.y, x * t.y y * t.x};}
}a[N], b[N];
int rev[N], bit, tot;
void fft(Complex a[], int inv)
{for (int i 0; i tot; i )if (i rev[i])swap(a[i], a[rev[i]]);for (int mid 1; mid tot; mid 1){auto w1 Complex({cos(PI / mid), inv * sin(PI / mid)});for (int i 0; i tot; i mid * 2){auto wk Complex({1, 0});for (int j 0; j mid; j , wk wk * w1){auto x a[i j], y wk * a[i j mid];a[i j] x y, a[i j mid] x - y;}}}
}
void init(){tot 1 bit;for (int i 0; i tot; i )rev[i] ((rev[i 1] 1)) | ((i 1) (bit - 1));
}
int n,m500000;
void solve(){cinn;for(int i1;in;i){int u;cinu;a[u].x1;b[500000-u].x1;}while((1bit)2*m1) bit;init();fft(a,1);fft(b,1);for(int i0;itot;i) a[i]a[i]*b[i];fft(a,-1);// for(int i500000;i500000-5;i--) cout(int)((a[i].x/tot)0.5)endl;for(int in;i500001;i){int f1;for(int ji;j500001;ji) if((int)((a[500000-j].x/tot)0.5)0){f0;break;}if(f){couti\n;break;}}
}int main()
{iosint T1;//cinT;//T1;while(T--){solve();}return 0;
}
