// 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;}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 2.296 ms | 16 MB + 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 84.506 ms | 18 MB + 456 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 40.935 ms | 16 MB + 820 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 41.033 ms | 16 MB + 808 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 2.297 ms | 16 MB + 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 2.3 ms | 16 MB + 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 2.299 ms | 16 MB + 28 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 79.156 ms | 18 MB + 188 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 78.903 ms | 18 MB + 188 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 73.212 ms | 17 MB + 944 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 85.242 ms | 18 MB + 536 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 85.569 ms | 17 MB + 416 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 2.299 ms | 16 MB + 28 KB | Accepted | Score: 0 | 显示更多 |