萌新求助五次拆系数 FFT 样例过但爆零
  • 板块学术版
  • 楼主junxis
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/8/23 18:52
  • 上次更新2023/10/27 13:59:21
查看原帖
萌新求助五次拆系数 FFT 样例过但爆零
551375
junxis楼主2022/8/23 18:52

RT\mathtt{RT}

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr << "Debug in line " << __LINE__  << " : "<< #x << " = " << x << "\n"
typedef long long ll;

typedef long double db;
const int FFT_MAXN=100005;
struct cp {
	db a, b;
	cp() :  a(0), b(0) {}
	cp(db a_) :  a(a_), b(0) {}
	cp(db a_, db b_) :  a(a_), b(b_) {}
	cp operator+(const cp&y) const { return (cp){a+y.a, b+y.b}; }
	cp operator-(const cp&y) const { return (cp){a-y.a, b-y.b}; }
	cp operator*(const cp&y) const { return (cp){a*y.a-b*y.b, a*y.b+b*y.a}; }
	cp operator!() const { return cp(a, -b); }
};

const db pi = acos(-1.0);

int bitrev[FFT_MAXN+10];

void dft(cp *a, int n, int flag=1) {
	for (int i = 0; i < n; i++) bitrev[i] = (bitrev[i>>1]>>1) | ((i&1)*(n>>1));
	for (int i = 0; i < n; i++) if (i < bitrev[i]) swap(a[i], a[bitrev[i]]);
	for (int l = 2; l <= n; l <<= 1) {
		cp del(cos(2.0*pi/l), sin(2.0*flag*pi/l));
		for (int i = 0; i < n; i += l) {
			cp ome(1,0), t, r;
			for (int k = i; k < i + (l>>1); k++, ome = ome * del) {
				t = a[k], r = a[k+(l>>1)] * ome;
				a[k] = t + r;
				a[k + (l>>1)] = t - r;
			}
		}	
	}
}

void convomod(ll *a, int n, ll *b, int m, ll *c, ll mo) {
	static cp f[FFT_MAXN], cf[FFT_MAXN], g[FFT_MAXN];
	int nn=1; while (nn < n + m) nn <<= 1;
	for (int i = 0; i <= n; i++) {
		f[i] = cp((db)(a[i]>>15), (db)(a[i]&32767));
		cf[i] = !f[i];
	}
	for (int i = 0; i <= m; i++) {
		g[i] = cp((db)(b[i]>>15), (db)(b[i]&32767));
	}
	dft(f, nn); dft(cf, nn); dft(g, nn);
	for (int i = 0; i < nn; i++) {
		g[i].a /= (db)nn; g[i].b /= (db)nn;
		f[i] = f[i] * g[i]; cf[i] = cf[i] * g[i];
	}
	dft(f, nn, -1); dft(cf, nn, -1);
	for (int i = 0; i <= n + m; i++) {
		ll aa, bb, cc, dd;
		aa = ll((f[i].a + cf[i].a)*0.5+0.5) % mo;
		bb = ll((f[i].b + cf[i].b)*0.5+0.5) % mo;
		cc = (ll(f[i].b+0.5) - bb) % mo;
		dd = (ll(cf[i].a+0.5) - aa) % mo;
		c[i] = ((aa*32767 + (bb+cc))*32767 + dd) % mo;
		if (c[i] < 0) c[i] += mo;
	}
}

ll a[FFT_MAXN], b[FFT_MAXN], ans[FFT_MAXN];

int main() {
	int n, m;
	ll p;
	scanf("%d%d%lld",&n,&m,&p);
	for (int i = 0; i <= n; i++) scanf("%lld",a+i);
	for (int i = 0; i <= m; i++) scanf("%lld",b+i);
	convomod(a, n, b, m, ans, p);
	for (int i = 0; i <= n + m; i++) printf("%lld%c",ans[i]," \n"[i==n+m]);
}
2022/8/23 18:52
加载中...