提交记录 19491


用户 题目 状态 得分 用时 内存 语言 代码长度
x383494 1002i. 【模板题】多项式乘法 Accepted 100 85.569 ms 18968 KB C++ 3.18 KB
提交时间 评测时间
2023-05-30 22:45:57 2023-05-31 22:34:46
// P3803
// 三次变两次CNTT, MOD 0x7fffFfff, i^2 = 3
#include <cstdio>
#include <algorithm>
#include <vector>
#define UP(i, s, e) for(auto i=s; i!=e; ++i)
#define NDEBUG 1
#define DEBUG 1
#define COMPLEX_MUL_FAST 0
#define CNTT_MOD_FAST 0
namespace m{ // } 
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
constexpr int N = 1<<21;
constexpr ui MOD = 0x7fffFfff; //998244353;
constexpr int TIMES = 32;
constexpr int sqi = 3;
inline ui MODDD(ull x){
#if !(CNTT_MOD_FAST)
	return x%MOD;
#endif
    x = x >= MOD ? (x&MOD) + (x >> 31) : x;
    x = x >= MOD ? (x&MOD) + (x >> 31) : x;
    x = x >= MOD ? x - MOD : x;
    return x;
}
inline ui MODDD(ui x){
	if(x>(MOD<<1)) x-=(MOD<<1);
	if(x>MOD) x-=MOD;
	return x;
}
struct CC{
	ui real, imag;
	CC(ui r = 0, ui i = 0){
		real = MODDD(r); 
        imag = MODDD(i);
	}
	CC& operator=(CC b){ real = MODDD(b.real);
	   	imag = MODDD(b.imag); return *this; }
	CC& operator=(ui b){ real = MODDD(b); imag = 0; return *this;}
	CC& operator+=(CC b){ 
		real = MODDD(real + b.real);
		imag = MODDD(imag + b.imag);
		return *this; 
    }
	CC& operator-=(CC b){ 
		real = MODDD(real + MOD - b.real);
		imag = MODDD(imag + MOD - b.imag);
		return *this; }
	CC operator-(CC b){ CC tmp = *this; return tmp-=b; }
	CC& operator*=(CC b){
#if COMPLEX_MUL_FAST
        ull x = ((ull)real + imag) * (b.real + b.imag);
        ull y = real * (ull) b.real;
        ull z = imag * (ull) b.imag;
		ull rr = y + z + (z << 1);
        ull ii = x-y-z;
#else
		ull rr = (ull)real * b.real + (ull)imag * b.imag * 3;
		ull ii = (ull)real * b.imag + (ull)imag * b.real;
#endif
        real = MODDD(rr);
        imag = MODDD(ii);
		return *this;
	}
	CC operator*(CC b){ CC tmp = *this; return tmp*=b; }
};
CC qpow(CC a, ull t){
	CC ans = CC(1);
	while(t){
		if(t&1) ans *= a;
		a *= a;
		t >>= 1;
	}
	return ans;
}
static CC const ROOT = qpow(CC(1, 1), MOD>>1);
//template<typename T, typename R>
//T qpow(T a, R t){
//	T ans = T(1);
//	while(t){
//		if(t&1) ans *= a;
//		a *= a;
//		t >>= 1;
//	}
//	return ans;
//}
CC inverse(ui x){
	return qpow(CC(x), MOD-2);
}
inline CC MODDD(CC x){ return CC(MODDD(x.real), MODDD(x.imag)); }
void change(CC *y, int len){
	static int rev[N];
	rev[0] = 0;
	UP(i, 1, len){
		rev[i] = rev[i>>1] >> 1;
		if(i&1) rev[i] |= len>>1;
	}
	UP(i, 0, len){
		if(i < rev[i]) std::swap(y[i], y[rev[i]]);
	}
}
void cntt(CC *y, int len, bool idft = false){
	change(y, len);
	for(int h_=1; (1<<h_)<=len; h_++){
        int h = 1 <<  h_;
		CC wn = qpow(ROOT, 1ull << (TIMES - h_));
		for(int j=0; j<len; j += h){
			CC w = 1;
			UP(k, j, j+h/2){
				CC t = w * y[k+h/2];
				y[k+h/2] = y[k] - t;
				y[k] += t;
				w *= wn;
			}
		}
	}
	if(idft){
		std::reverse(y+1, y+len);
		CC il = inverse(len);
		UP(i, 0, len){
			y[i] *= il;
		}
	}
}
CC ia[N];
int in, im;
void work(){
#if DEBUG
	qpow(CC(1,1), 8191);
#endif
	scanf("%d%d", &in, &im);
	UP(i, 0, in+1) scanf("%u", &ia[i].real);
	UP(i, 0, im+1) scanf("%u", &ia[i].imag);
	int len = 1;
	while(len <= in+im) len <<= 1;
	cntt(ia, len, false);
	UP(i, 0, len){
		ia[i] *= ia[i];	
	}
	cntt(ia, len, true);
	UP(i, 0, in+im+1){
        static ui inv2 = inverse(2).real;
		printf("%u ", MODDD(inv2 * (ull)ia[i].imag));
	}
}
} int main(){ m::work(); return 0;}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #12.296 ms16 MB + 28 KBAcceptedScore: 0

Subtask #1 Testcase #284.506 ms18 MB + 456 KBAcceptedScore: 100

Subtask #1 Testcase #340.935 ms16 MB + 820 KBAcceptedScore: 0

Subtask #1 Testcase #441.033 ms16 MB + 808 KBAcceptedScore: 0

Subtask #1 Testcase #52.297 ms16 MB + 28 KBAcceptedScore: 0

Subtask #1 Testcase #62.3 ms16 MB + 28 KBAcceptedScore: 0

Subtask #1 Testcase #72.299 ms16 MB + 28 KBAcceptedScore: 0

Subtask #1 Testcase #879.156 ms18 MB + 188 KBAcceptedScore: 0

Subtask #1 Testcase #978.903 ms18 MB + 188 KBAcceptedScore: 0

Subtask #1 Testcase #1073.212 ms17 MB + 944 KBAcceptedScore: 0

Subtask #1 Testcase #1185.242 ms18 MB + 536 KBAcceptedScore: 0

Subtask #1 Testcase #1285.569 ms17 MB + 416 KBAcceptedScore: 0

Subtask #1 Testcase #132.299 ms16 MB + 28 KBAcceptedScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-28 21:38:26 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用