我觉得我该把这玩意发出来以便在 cnblogs 抽风时能看到
header.cpp
#include <bits/stdc++.h>
using namespace std; using pii = pair<int,int>; using vi = vector<int>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> T rand(T l, T r) { return uniform_int_distribution<T>(l, r)(rnd); }
template <typename T> void get(T & x) {
x = 0; char ch = getchar(); bool f = false; while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x);
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
template <typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
template <typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define ufile(x)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define Aster(i, s) for (int i = head[s], v; i; i = e[i].next)
#define all(s) s.begin(), s.end()
#define eb emplace_back
#define pb pop_back
#define em emplace
const int N = 2e5 + 100;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
// int mod;
// int fac[N], inv[N], ifac[N];
// const int mod = ;
const int mod = 998244353; // const int g = 3;
// const int mod = 1e9 + 7;
// const int mod = 1e9 + 9;
// const int mod = 1e9 + 3579, bse = 131;
/* add / sub */ template <typename T1, typename T2> T1 add(T1 a, T2 b) { return (a += b) >= mod ? a - mod : a; } template <typename T1, typename ...Args> T1 add(T1 a, Args ... b) { return add(a, add(b...)); } template <typename T1, typename T2> T1 sub(T1 a, T2 b) { return (a -= b) < 0 ? a + mod : a; } template <typename T1, typename ...Args> T1 sub(T1 a, Args ... b) { return add(a, add(b...)); } template <typename T1, typename T2> void addi(T1 & a, T2 b) { (a += b) >= mod ? (a -= mod) : true; } template <typename T1, typename ...Args> void addi(T1 & a, Args ...b) { addi(a, add(b...)); } template <typename T1, typename T2> void subi(T1 & a, T2 b) { (a -= b) < 0 ? (a += mod) : true; } template <typename T1, typename ...Args> void subi(T1 & a, Args ...b) { subi(a, add(b...)); }
/* Fastmod / mul */ struct FastMod { int m; ll b; void init(int _m) { m = _m; if (m == 0) m = 1; b = ((lll)1<<64) / m; } FastMod(int _m) { init(_m); } int operator() (ll a) {ll q = ((lll)a * b) >> 64; a -= q * m; if (a >= m) a -= m; return a; } } Mod(mod); int mul(int a, int b) { return Mod(1ll * a * b); } template <typename T1, typename T2> int mul(T1 a, T2 b) { return Mod((long long)(1ll * a * b)); } template <typename T, typename ...Args> int mul(T a, Args ...b) { return mul(a, mul(b...)); } template <typename T1, typename T2> void muli(T1 & a, T2 b) { a = Mod(1ll * a * b); } template <typename T1, typename ...Args> void muli(T1 & a, Args ...b) { muli(a, mul(b ...)); } // /* trivial multiple function(idk whether its useful*/ int mul(int a, int b) { return 1ll * a * b % mod; } template <typename T1, typename T2> int mul(T1 a, T2 b) { return (long long)(1ll * a * b) % mod; } template <typename T, typename ...Args> int mul(T a, Args ...b) { return mul(a, mul(b...)); }
/* qp init C */ template <typename T1, typename T2> T1 qp(T1 a, T2 b) { T1 ret = 1; for (; b > 0; a = mul(a, a), b >>= 1) if (b & 1) ret = mul(ret, a); return ret; } template<typename T1> void init_fac(T1 bnd) { static int __var_bound; if (__var_bound == 0) fac[0] = inv[0] = ifac[0] = fac[1] = inv[1] = ifac[1] = __var_bound = 1; rep(i, __var_bound + 1, bnd) fac[i] = mul(fac[i - 1], i), inv[i] = mul(mod - mod / i, inv[mod % i]);rep(i, __var_bound + 1, bnd) ifac[i] = mul(ifac[i - 1], inv[i]); __var_bound = bnd; } template<typename T1, typename T2> int C(T1 n, T2 m) { if (n < m or m == 0) return 1; init_fac(max(n, m)); return mul(fac[n], ifac[m], ifac[n - m]); }
/* inv 2/3/6 / phi */ constexpr int __var_pow(int a, int b) { int ret = 1; for (; b > 0; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ret = 1ll * ret * a % mod; return ret; } constexpr int __var_phi(int x) { if (x <= 2) return 1; int ret = x; for (int i = 2; 1ll * i * i <= x; ++i) if (x % i == 0) { ret = ret / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) ret = ret / x * (x - 1); return ret; } const int __phi_mod = __var_phi(mod); const int inv2 = __var_pow(2, __phi_mod - 1), inv3 = __var_pow(3, __phi_mod - 1), inv6 = __var_pow(6, __phi_mod - 1); constexpr int __var_check() { assert( 1ll * 2 * inv2 % mod == 1 ); assert( 1ll * 3 * inv3 % mod == 1 ); assert( 1ll * 6 * inv6 % mod == 1 ); return (unsigned int)(-1); } const int __var_dummy = __var_check();
signed main() {
file();
}
cr.cpp
/*
g++ std.cpp -o std -Wall -Wextra -Wshadow -fsanitize=undefined,address,leak
*/
#include <bits/stdc++.h>
#include<chrono>
using namespace std;
using namespace std::chrono;
void col(int id) { printf("\033[3%dm", id); }
string stat;
char ch;
signed main() {
int __LIMIT__ = 1000, __CNT__ = 0, __AC__ = 0, __WA__ = 0;
putchar(10);
system("g++ bf.cpp -o bf -std=c++14 -Ofast");
system("g++ std.cpp -o std -std=c++14 -O2 -fsanitize=undefined,address,leak");
system("g++ da.cpp -o da -std=c++14 -Ofast");
for (int i = 1; i < __LIMIT__; i++) {
col(9), printf("#No:%4d | ", i);
system("./da > a.in");
auto beg = steady_clock::now();
system("./std < a.in > as.out");
auto ed = steady_clock::now();
system("./bf < a.in > ab.out");
if (system("diff ab.out as.out -q -B -w")) {
col(1), printf("Wrong Answer"), col(9);
__LIMIT__ *= 0.65;
__WA__++;
}
else {
col(2), printf("Accepted"), col(9);
__CNT__++;
if (__CNT__ == 10) __CNT__ = 0, __LIMIT__ ++;
__AC__++;
}
auto gap = duration_cast< duration<double,ratio<1,1000> > > (ed-beg);
printf(" | %.4lf\n", gap.count());
} col(9);
printf("SUM : %d | AC : %d | WA : %d\nAccepting Rate : %lf\n", __AC__ + __WA__, __AC__, __WA__, 1.0 * __AC__ / (__AC__ + __WA__));
/*
system("g++ std.cpp -o std -std=c++14 -fsanitize=undefined,address,leak");
system("g++ da.cpp -o da -std=c++14 -Ofast");
system("g++ checker.cpp -o checker -std=c++14 -O2");
for (int i = 1; i < __LIMIT__; i++) {
col(9), printf("#No:%4d | ", i);
system("./da > a.in");
long long beg = time();
system("./std < a.in > as.out");
long long ed = time();
system("./checker > stat.out");
freopen("stat.out", "r", stdin);
cin >> stat;
if (stat == "OK") {
col(2), printf("Accepted"), col(9);
__CNT__++;
if (__CNT__ == 10) __CNT__ = 0, __LIMIT__ ++;
__AC__++;
} else {
col(1), cout << stat, col(9);
__LIMIT__ *= 0.65;
__WA__++;
} printf(" | %.4lf\n", 1. * (ed - beg) / CLOCKS_PER_SEC);
fclose(stdin);
} col(9);
printf("SUM : %d | AC : %d | WA : %d\nAccepting Rate : %lf\n", __AC__ + __WA__, __AC__, __WA__, 1.0 * __AC__ / (__AC__ + __WA__));
*/
putchar(10);
}
gen.cpp
#include <bits/stdc++.h>
// namespace Fread { const int SIZE = (1 << 18); char buf[SIZE], *p1 = buf, *p2 = buf; inline char getchar() {return (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, SIZE, stdin), p1 == p2) ? EOF : *p1++);} }
// namespace Fwrite { const int SIZE = (1 << 18); char buf[SIZE], *S = buf, *T = buf+SIZE; inline void flush(){ fwrite(buf, 1, S-buf, stdout), S = buf; } struct NTR{ ~NTR() { flush(); } }ztr;inline void putchar(char c){ *S++ = c; if(S == T) flush(); } }
// #ifdef ONLINE_JUDGE
// #define getchar Fread::getchar
// #define putchar Fwrite::putchar
// #endif
// namespace Fastio{
// struct Reader{ template <typename T> Reader & operator >> (T & x) {char c = getchar(); bool f = false;while (c < '0' or c > '9') { if (c == '-') f = true;c = getchar();} x = 0;while(c >= '0' and c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} if (f) x = -x;return *this;}Reader&operator>>(char&c){ c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){ int len=0;char c=getchar(); while(c=='\n'||c==' '||c=='\r')c=getchar(); while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar(); str[len]='\0'; return *this;}Reader & operator >> (float & x) {char c=getchar();short f=1,s=0;x=0;double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader & operator >> (double & x) {char c=getchar();short f=1,s=0;x=0;double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(long double&x){char c=getchar();short f=1,s=0;x=0;long double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(__float128&x){char c=getchar();short f=1,s=0;x=0;__float128 t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.') c = getchar();else return x*=f, *this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return *this;}Reader(){}}cin;
// struct Writer{ template <typename T> Writer & operator << (T x) {if(x == 0) return putchar('0'), *this;if(x < 0) putchar('-'), x = -x;static int sta[60], top = 0; while (x) sta[++top] = x %10, x /= 10; while (top) putchar(sta[top] + '0'), --top; return *this;} Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;} typedef unsigned long long mxdouble; int precision = 6; Writer set_precision(int val) { precision = val; return *this; }template <typename T> T deal_precision(T x) {__float128 tmp = x;for(int i=0;i<=precision;i++)tmp*=10;tmp+=5;for(int i=0;i<=precision;i++) tmp/=10;return (T)tmp;}Writer&operator<<(float x){if(x<0)putchar('-'),x=-x; x=deal_precision(x); mxdouble _=x;x-=(__float128)_;static int sta[60];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;if(precision==0)return*this;putchar('.');for(int i=0;i<=precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}Writer&operator<<(double x){if(x<0)putchar('-'),x=-x; x = deal_precision(x); mxdouble _=x;x-=(double)_;static int sta[60];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;if(precision==0)return*this;putchar('.');for(int i=0;i<precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x; x = deal_precision(x); mxdouble _=x;x-=(__float128)_;static int sta[60];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;if(precision==0)return*this;putchar('.');for(int i=0;i<precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x; x = deal_precision(x); mxdouble _=x;x-=(__float128)_;static int sta[60];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;if(precision==0)return*this;putchar('.');for(int i=0;i<precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}Writer(){}}cout;
// } const char * endl = "\n"; const char * space = " ";
// #define cin Fastio :: cin
// #define cout Fastio :: cout
#define int long long
#define rep(i,a,b) for (register int (i) = (a); (i) <= (b); ++(i))
#define pre(i,a,b) for (register int (i) = (a); (i) >= (b); --(i))
using namespace std;
const int mod = 998244353;
int T, n, m, rge;
set<pair<int,int> > st;
char fi[] = "1_01.in";
char fo[] = "1_01.out";
char tmp[] = "resdata.res";
mt19937_64 rnd(random_device{}());
void run(const char fi[], const char fo[]) {
string str;
str += "./std < ";
str += fi;
str += " > ";
str += fo;
system(str.c_str());
}
bool check(const char fi[], const char fo[]) {
string str;
str += "./xin < ";
str += fi;
str += " > a.out";
system(str.c_str());
str.clear();
str += "diff ";
str += fo;
str += " a.out -q -B -w";
return system(str.c_str());
}
int readIn(const char fi[]) {
freopen(fi, "r", stdin);
int ret; cin >> ret;
fclose(stdin);
return ret;
}
int ans[400005];
void encrypt(const char infl[], const char outfl[], const char output[], int ans_cnt) {
freopen(outfl, "r", stdin);
rep(i,1,ans_cnt) {
cin >> ans[i];
if (ans[i] == -1) ans[i] = 0;
}
fclose(stdin);
freopen(infl, "r", stdin);
freopen(output, "w", stdout);
int n, q, s, t1, t2, t3, nowans = 0;
cin >> n >> q >> s; cout << n << ' ' << q << ' ' << s << '\n';
rep(i,1,n) cin >> t1, cout << t1 << ' '; cout << '\n';
rep(i,2,n) cin >> t1 >> t2, cout << t1 << ' ' << t2 << '\n';
rep(i,1,q) {
cin >> t1;
if (t1 == 1) {
cin >> t2;
if (s) t1 ^= ans[nowans], t2 ^= ans[nowans];
cout << t1 << ' ' << t2 << '\n';
} else {
cin >> t2 >> t3;
if (s) t1 ^= ans[nowans], t2 ^= ans[nowans], t3 ^= ans[nowans];
cout << t1 << ' ' << t2 << ' ' << t3 << '\n';
}
if (s) if ((t1 ^ ans[nowans]) > 2) ++ nowans;
}
fclose(stdin);
fclose(stdout);
}
void genTree(int n) {
rep(i,2,n) cout << i << ' ' << (rand() % (i - 1) + 1) << '\n';
}
void genChain(int n) {
rep(i,2,n) cout << i << ' ' << i - 1 << '\n';
}
void genStick(int n, int prag) {
genTree(15);
rep(i,16,n) cout << i << ' ' << ((rand() % prag + 1) + (i - prag - 1)) << '\n';
}
int vis[400050];
int rng(int l, int r) { return uniform_int_distribution<>(l, r)(rnd); }
void taskGen(int kl, int kr, int nl, int nr, int vall, int slim) {
int k = rnd() % (kr - kl + 1) + kl, n = rnd() % (nr - nl + 1) + nl;
int st0 = rng(-vall, vall), st1 = rng(-vall, vall),
a = rng(-vall, vall), b = rng(-vall, vall), s = rng(-vall, vall);
if (slim) s = 1;
cout << k << ' ' << n << '\n';
cout << st0 << ' ' << st1 << ' ' << a << ' ' << b << ' ' << s << '\n';
rep(i,1,k-1) cout << (slim ? 1 : rng(-vall, vall)) << ' '; cout << '\n';
}
void subtask(int id_subtask, int idl, int idr, int kl, int kr, int nl, int nr, int vall, int slim) {
fi[0] = fo[0] = id_subtask + '0';
rep(id, idl, idr) {
// int n = __N, m = rand() % __M + __N;
fi[2] = fo[2] = (id / 10) % 10 + '0', fi[3] = fo[3] = id % 10 + '0';
cerr << "START GEN : #Sub. " << (long long)id_subtask << " #No. " << (long long)id << '\n';
freopen(fi, "w", stdout);
taskGen(kl, kr, nl, nr, vall, slim);
fclose(stdout);
run(fi, fo);
cerr << "COMPLETED : #Sub. " << (long long)id_subtask << " #No. " << (long long)id << '\n';
}
cerr << "Subtask " << (long long)id_subtask << " COMPLETED." << '\n';
}
signed main() {
srand(rnd());
system("g++ std.cpp -o std -O2");
cerr << "START" << '\n';
subtask(1, 1, 5, 50, 100, 50, 100, 1000, 0);
subtask(1, 6, 10, 75, 100, 80, 100, mod - 1, 0);
subtask(2, 1, 5, 90, 100, (1ull << 60), (1ull << 63) - 1, 10000, 0);
subtask(2, 6, 10, 95, 100, (1ull << 62), (1ull << 63) - 1, mod - 1, 0);
subtask(3, 1, 5, 4005, 5000, (1ull << 60), (1ull << 63) - 1, 10000, 1);
subtask(3, 6, 9, 4500, 5000, (1ull << 62), (1ull << 63) - 1, mod - 1, 1);
subtask(3, 10, 10, 5000, 5000, (1ull << 63) - 2, (1ull << 63) - 1, mod - 1, 1);
subtask(4, 1, 7, 4950, 5000, (1ull << 62), (1ull << 63) - 1, mod >> 1, 0);
subtask(4, 8, 15, 4999, 5000, (1ull << 63) - 10, (1ull << 63) - 1, mod - 1, 0);
return 0;
}
boards/
anymod_fft:
using ll = int64_t;
using db = double;
struct cp {
db x, y;
cp(db real = 0, db imag = 0) : x(real), y(imag){};
cp operator+(cp b) const { return {x + b.x, y + b.y}; }
cp operator-(cp b) const { return {x - b.x, y - b.y}; }
cp operator*(cp b) const { return {x * b.x - y * b.y, x * b.y + y * b.x}; }
};
using vcp = vector<cp>;
namespace FFT {
const db pi = acos(-1);
vcp Omega(int L) {
vcp w(L); w[1] = 1;
for (register int i = 2; i < L; i <<= 1) {
auto w0 = w.begin() + i / 2, w1 = w.begin() + i;
cp wn(cos(pi / i), sin(pi / i));
for (register int j = 0; j < i; j += 2)
w1[j] = w0[j >> 1], w1[j + 1] = w1[j] * wn;
} return w;
} auto W = Omega(1 << 21);
void DIF(cp *a, int n) {
cp x, y;
for (register int k = n >> 1; k; k >>= 1)
for (register int i = 0; i < n; i += k << 1)
for (register int j = 0; j < k; ++j)
x = a[i + j], y = a[i + j + k],
a[i + j + k] = (x - y) * W[k + j], a[i + j] = x + y;
}
void IDIT(cp *a, int n) {
cp x, y;
for (register int k = 1; k < n; k <<= 1)
for (register int i = 0; i < n; i += k << 1)
for (register int j = 0; j < k; ++j)
x = a[i + j], y = a[i + j + k] * W[k + j],
a[i + j + k] = x - y, a[i + j] = x + y;
const db Inv = 1. / n;
rep(i, 0, n - 1) a[i].x *= Inv, a[i].y *= Inv;
reverse(a + 1, a + n);
}
}
namespace Polynomial {
using poly = vector<int>;
void DFT(vcp &a) { FFT::DIF(a.data(), a.size()); }
void IDFT(vcp &a) { FFT::IDIT(a.data(), a.size()); }
int norm(int n) { return 1 << (__lg(n - 1) + 1); }
poly operator*(poly &a, poly &b) {
int n = a.size() + b.size() - 1;
vcp c(norm(n));
rep(i, 0, a.size() - 1) c[i].x = a[i];
rep(i, 0, b.size() - 1) c[i].y = b[i];
DFT(c);
rep(i, 0, a.size() - 1) c[i] = c[i] * c[i];
IDFT(c), a.resize(n);
rep(i, 0, n - 1) a[i] = int(c[i].y * .5 + .5);
return a;
}
poly conv(const poly &a, const poly &b, const int&P) {
int n = a.size(), m = b.size(), o = n + m - 1, l = norm(o);
vcp A(l), B(l), c0(l), c1(l);
for (register int i = 0; i < n; i++) A[i] = cp(a[i] & 0x7fff, a[i] >> 15);
for (register int i = 0; i < m; i++) B[i] = cp(b[i] & 0x7fff, b[i] >> 15);
FFT::DIF(A.data(), l), FFT::DIF(B.data(), l);
for (register int k = 1, i = 0, j; k < l; k <<= 1)
for (register ; i < k * 2; i++) {
j = i ^ k - 1;
c0[i] = cp(A[i].x + A[j].x, A[i].y - A[j].y) * B[i] * 0.5;
c1[i] = cp(A[i].y + A[j].y, -A[i].x + A[j].x) * B[i] * 0.5;
}
FFT::IDIT(c0.data(), l), FFT::IDIT(c1.data(), l);
poly res(o);
for (register int i = 0; i < o; i++) {
ll c00 = c0[i].x + 0.5, c01 = c0[i].y + 0.5, c10 = c1[i].x + 0.5, c11 = c1[i].y + 0.5;
res[i] = (c00 + ((c01 + c10) % P << 15) + (c11 % P << 30)) % P;
}
return res;
}
} using namespace Polynomial;
poly F[N];
fwt:
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define rep(i,a,b) for (register int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define pre(i,a,b) for (register int i = (a), i##_ = (b) - 1; i > i##_; --i)
const int N = 1e6 + 10, mod = 998244353, inv2 = 499122177;
int n, m, a[1 << 17], b[1 << 17], A[1 << 17], B[1 << 17], C[1 << 17];
inline void OR(int f[], int limit, int type = 1) {
for (int mid = 1, len = 2; len <= limit; mid <<= 1, len <<= 1) {
for (int i = 0; i < limit; i += len) {
for (int j = 0; j < mid; ++ j) {
f[i + j + mid] = (f[i + j + mid] + 1ll * f[i + j] * type) % mod;
}
}
}
}
inline void AND(int f[], int limit, int type = 1) {
for (int mid = 1, len = 2; len <= limit; mid <<= 1, len <<= 1) {
for (int i = 0; i < limit; i += len) {
for (int j = 0; j < mid; ++ j) {
f[i + j] = (f[i + j] + 1ll * f[i + j + mid] * type) % mod;
}
}
}
}
inline void XOR(int f[], int limit, int type = 1) {
for (int mid = 1, len = 2; len <= limit; mid <<= 1, len <<= 1) {
for (int i = 0; i < limit; i += len) {
for (int j = 0; j < mid; ++ j) {
f[i + j] = (f[i + j] + f[i + j + mid]) % mod;
f[i + j + mid] = (1ll * f[i + j] - f[i + j + mid] - f[i + j + mid] + (mod << 1)) % mod;
f[i + j] = 1ll * f[i + j] * type % mod;
f[i + j + mid] = 1ll * f[i + j + mid] * type % mod;
}
}
}
}
void getFWT(int A[], int B[], int C[], int type) {
for (int i = 0; i < n; ++ i) a[i] = A[i];
for (int i = 0; i < n; ++ i) b[i] = B[i];
if (type == 1) OR(a, n, 1), OR(b, n, 1);
if (type == 2) AND(a, n, 1), AND(b, n, 1);
if (type == 3) XOR(a, n, 1), XOR(b, n, 1);
for (int i = 0; i < n; ++ i) a[i] = 1ll * a[i] * b[i] % mod;
if (type == 1) OR(a, n, mod - 1);
if (type == 2) AND(a, n, mod - 1);
if (type == 3) XOR(a, n, inv2);
for (int i = 0; i < n; ++ i) C[i] = a[i];
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> m; n = 1 << m;
for (int i = 0; i < n; ++ i) cin >> A[i];
for (int i = 0; i < n; ++ i) cin >> B[i];
getFWT(A, B, C, 1);
for (int i = 0; i < n; ++ i) cout << C[i] << ' '; cout << endl;
getFWT(A, B, C, 2);
for (int i = 0; i < n; ++ i) cout << C[i] << ' '; cout << endl;
getFWT(A, B, C, 3);
for (int i = 0; i < n; ++ i) cout << C[i] << ' '; cout << endl;
}
polynomial:
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define rep(i, a, b) for (register int(i)=(a), i##_=(b) + 1; (i)<i##_; ++(i))
#define pre(i, a, b) for (register int(i)=(a), i##_=(b) - 1; (i) > i##_; --(i))
using namespace std;
const int N=3e5 + 10, mod=998244353, g=3;
const int siz_int=sizeof(int);
#ifdef ONLINE_JUDGE
char buf[1<<21], *p1=buf, *p2=buf; inline char getc() { return (p1 == p2 && (p2=(p1=buf) + fread(buf, 1, 1<<21, stdin), p1 == p2) ? EOF : *p1++); }
#define getchar getc
#endif
template <typename T> inline void get(T&x){
x=0; char ch=getchar(); bool f=false; while (ch<'0' or ch > '9') f=f or ch == '-', ch=getchar();
while (ch >= '0' and ch <= '9') x=(x<<1) + (x<<3) + (ch^48), ch=getchar(); f && (x=-x);
} template <typename T, typename ... Args> inline void get(T&x, Args&... _Args) { get(x); get(_Args...); }
int n, m, len=1, a[N], cnt[N], ifv[N];
typedef long long ll; typedef __int128 lll;
struct FastMod { int m; ll b; FastMod(int _m) { m=_m; b=((lll)1<<64) / m; } int operator() (ll a) {ll q=((lll)a*b) >> 64; a -= q*m; if (a >= m) a -= m; return a; } } Mod(mod);
int add(int a, int b) { return (a += b) >= mod ? a - mod : a; } template <typename ...Args> int add(int a, Args ...b) { return add(a, add(b...)); }
int mul(int a, int b) { return Mod(1ll*a*b); } template <typename ...Args> int mul(int a, Args ...b) { return mul(a, mul(b...)); }
int btrs[N << 1];
inline int initrs(int k) {
int limit=1;
while (limit<k) limit <<= 1;
for (register int i=0 ;i<limit; i ++) btrs[i]=(btrs[i >> 1] >> 1) | ((i&1) ? limit >> 1 : 0);
return limit;
}
inline int qp(int a, int b) {
int ret=1;
while (b) {
if (b&1) ret=mul(ret, a);
a=mul(a, a);
b >>= 1;
} return ret;
} inline int inv(int a) { return qp(a, mod-2); }
const int invg=inv(g), inv2=(mod + 1) >> 1;
const int L=1 << 21;
int w[2][L];
int IUR() {
w[0][0]=w[1][0]=1; int wn=qp(g, (mod-1) / L);
for (register int i=1;i<L; i++) w[0][L - i]=w[1][i]=mul(w[1][i - 1], wn);
return 1;
} int dummy=IUR();
struct poly {
vector <int> f;
int operator [] (const int&pos) const { return f[pos]; }
int&operator [] (const int&pos) { return f[pos]; }
int deg() {return f.size(); }
int deg() const {return f.size(); }
void Set(int n) { f.resize(n); }
void Adjust() { while (f.size() > 1 and f.back() == 0) f.pop_back(); }
void Reverse() { reverse(f.begin(), f.end()); }
void scan(int n=-1) { if (n<0) get(n); Set(n); for (register int i=0;i<n; i++) get(f[i]); }
void print() { for (int x : f) printf("%d ", x); }
void getFac(int k) { Set(k); f[0]=1; for (int i=1; i <= k; i++) f[i]=mul(f[i - 1], i); }
void getInv(int k) { Set(k); f[0]=f[1]=1; for (int i=1; i <= k;++i) f[i]=mul(mod - mod / i, f[mod%i]); }
void deri() { for (register int i=0; i + 1<(int)f.size(); ++i) f[i]=mul(f[i+1], i+1); f.back()=0; }
void intg() { for (register int i=f.size() - 1; i >= 1; --i) f[i]=mul(f[i-1], inv(i)); f[0]=0; }
poly Deri() {
poly ret; ret.Set(deg());
for (int i=0; i + 1<deg(); ++i) {
ret[i]=mul(f[i+1], i+1);
} return ret;
} poly Intg() {
poly ret, inv; ret.Set(deg()), inv.getInv(deg() - 1);
for (int i=deg() - 1; i >= 1; --i) {
ret[i]=mul(f[i-1], inv[i]);
} return ret;
}
inline void NTT (const int lim, const int type) {
Set(lim);
for (register int i=0;i<lim; i++) if (i<btrs[i]) swap(f[i], f[btrs[i]]);
for (register int mid=1, y; mid<lim; mid <<= 1) {
for (register int i=L / (mid<<1), j=0; j<lim; j += (mid << 1)) {
for (register int k=0; k<mid; k++) {
y=mul(w[type][i*k], f[j + k + mid]);
f[j + k + mid]=add(f[j + k], mod - y);
f[j + k]=add(f[j + k], y);
}
}
} if (type == 1) return;
int inv=qp(lim, mod - 2);
for (register int i=0;i<lim; i++) f[i]=mul(f[i], inv);
}
friend poly operator + (const poly&x, const poly&y) {
poly ret; ret.Set(max(x.deg(), y.deg()));
for (register int i=0;i<x.deg(); ++i) ret[i]=x[i];
for (register int i=0;i<y.deg(); ++i) ret[i]=add(ret[i], y[i]);
return ret;
} void operator += (const poly&x) {
Set(max(deg(), x.deg()));
for (register int i=0;i<x.deg(); ++i) f[i]=add(f[i], x[i]);
}
friend poly operator - (const poly&x, const poly&y) {
poly ret; ret.Set(max(x.deg(), y.deg()));
for (register int i=0;i<x.deg(); ++i) ret[i]=x[i];
for (register int i=0;i<y.deg(); ++i) ret[i]=add(ret[i], mod - y[i]);
return ret;
} void operator -= (const poly&x) {
Set(max(deg(), x.deg()));
for (register int i=0;i<x.deg(); ++i) f[i]=add(f[i], mod - x[i]);
}
friend poly operator*(const poly&x, const poly&y) {
poly ret, A=x, B=y;
int limit=initrs(A.deg() + B.deg() - 1);
A.NTT(limit, 1), B.NTT(limit, 1); ret.Set(limit);
for (register int i=0;i<limit; i++) ret[i]=mul(A[i], B[i]);
ret.NTT(limit, 0); ret.Adjust();
return ret;
} void operator *= (const poly&x) {
poly A=x;
int limit=initrs(deg() + A.deg() - 1);
A.NTT(limit, 1); NTT(limit, 1);
for (register int i=0;i<limit; i++) f[i]=mul(A[i], f[i]);
NTT(limit, 0); Adjust();
}
friend poly operator / (const poly&x, const poly&y) {
poly A=x, B=y;
A.Reverse(), B.Reverse(); B.Set(x.deg() - y.deg() + 1);
B=B.Inv(); B *= A;
B.Set(x.deg() - y.deg() + 1); B.Reverse();
return B;
}
friend pair<poly,poly> operator%(const poly&x, const poly&y) {
poly A=x, B=y;
A.Reverse(), B.Reverse(); B.Set(x.deg() - y.deg() + 1);
B=B.Inv(); B *= A;
B.Set(x.deg() - y.deg() + 1); B.Reverse();
poly R=x - B*y; R.Set(y.deg() - 1);
return {B, R};
}
poly Inv() {
poly ret; ret.Set(1);
if (f.empty()) return ret;
ret[0]=inv(f[0]); poly A, B;
for (register int len=2, limit; len<(deg() << 1); len <<= 1) {
A.f.assign((*this).f.begin(), (*this).f.begin() + min(len, deg()));
B=ret; B.Set(min(len, deg()));
limit=initrs(A.deg() + B.deg() - 1);
A.NTT(limit, 1); B.NTT(limit, 1);
ret.Set(limit);
for (register int i=0;i<limit; i++) ret[i]=mul(add(2, mod - mul(A[i], B[i])), B[i]);
ret.NTT(limit, 0);
ret.Set(len);
} ret.Set(deg()); return ret;
}
poly Ln() {
poly ret=Deri(), Iv=Inv();
ret *= Iv; ret.intg(); ret.Set(deg());
return ret;
}
poly Exp() {
poly ret; ret.Set(1); ret[0]=1;
poly A, B;
for (register int len=2; len<(deg() << 1); len <<= 1) {
ret.Set(len); A=ret.Ln();
B.f.assign((*this).f.begin(), (*this).f.begin() + min(len, deg()));
B -= A; B[0]++; ret *= B;
ret.Set(len);
} ret.Set(deg()); return ret;
}
poly Sqrt() {
poly ret; ret.Set(1); ret[0]=1;
poly A, B;
for (register int len=2; len<(deg() << 1); len <<= 1) {
ret.Set(len); A=ret.Inv();
B.f.assign((*this).f.begin(), (*this).f.begin() + min(len, deg()));
A *= B;
for (int i=0;i<len; i++) ret[i]=mul(ret[i] + A[i], inv2);
ret.Set(len);
} ret.Set(deg()); return ret;
}
void getS2_line(int n) {
poly jc, inv, ret;
jc.getFac(n), inv.getInv(n);
poly A, B; A.Set(n + 1), B.Set(n + 1);
for (int i=0; i <= n; i++) A[i]=(i&1 ? mod - inv[i] : inv[i] ), B[i]=mul(qp(i,n), inv[i]);
(*this)=A*B;
Set(n + 1);
}
} F;
namespace __POLY__{
namespace tdef{typedef int i32;typedef unsigned int u32;typedef long long i64;typedef unsigned long long u64;typedef vector<i32>vi32;typedef vector<u32>vu32;typedef vector<i64>vi64;typedef vector<u64>vu64;}const int N=3e6+10,mod=998244353,gen=3;namespace math{using namespace tdef;template<typename T=int>inline T qp(i64 x,int y,i64 ans=1){for(y<0?y+=mod-1:0;y;y>>=1,x=x*x%mod)y&1?ans=ans*x%mod:0;return ans;}inline constexpr int lg(u32 x){return x==0?-1:((int)sizeof(int)*__CHAR_BIT__-1-__builtin_clz(x));}inline u32 fst_mul(u32 x,u64 p,u64 q){return x*p-(q*x>>32)*mod;}const u32 modm2=mod+mod;namespace basic_math{vu32 __fac({1,1}),__ifc({1,1}),__inv({0,1});inline void __prep(int n){static int i=2;if(i<n)for(__fac.resize(n),__ifc.resize(n),__inv.resize(n);i<n;i++)__fac[i]=1ll*i*__fac[i-1]%mod,__inv[i]=1ll*(mod-mod/i)*__inv[mod%i]%mod,__ifc[i]=1ll*__inv[i]*__ifc[i-1]%mod;}inline u32 gfac(u32 x){return __prep(x+1),__fac[x];}inline u32 gifc(u32 x){return __prep(x+1),__ifc[x];}inline u32 ginv(u32 x){return __prep(x+1),__inv[x];}}namespace cipolla{u32 I=0;struct cpl{u32 x,y;cpl(u32 _x=0,u32 _y=0):x(_x),y(_y){}inline cpl operator*(const cpl&a)const{return cpl((1ull*x*a.x+1ull*I*y%mod*a.y)%mod,(1ull*x*a.y+1ull*y*a.x)%mod);}};inline cpl cplpow(cpl a,int y,cpl b=cpl(1,0)){for(;y;y>>=1,a=a*a)if(y&1)b=b*a;return b;}inline u32 isqrt(u32 x){static mt19937 rnd(998244353);if(mod==2||!x||x==1)return x;u32 a=0;do{a=rnd()%mod;}while(qp((1ull*a*a+mod-x)%mod,mod>>1)!=mod-1);I=(1ll*a*a+mod-x)%mod;a=cplpow(cpl(a,1),(mod+1)>>1).x;return min(a,mod-a);}}using basic_math::gfac;using basic_math::gifc;using basic_math::ginv;using cipolla::isqrt;}namespace polynormial{using namespace tdef;const int maxbit=23;using math::lg,math::qp,math::gfac,math::gifc,math::ginv;namespace fast_number_theory_transform{using math::modm2,math::fst_mul;template<class T>inline void butterfly(T*p,int bit){for(u32 i=0,j=0;i<(1u<<bit);i++){if(i>j)swap(p[i],p[j]);for(u32 l=1u<<(bit-1);(j^=l)<l;l>>=1);}}u32*_p0[maxbit+1],*_p1[maxbit+1];inline void prep(int bit){static int k=0;u64 g;for(u32*p,*q,nl;k<bit;k++){nl=1<<k;g=qp(3,mod>>(k+1));p=_p0[k]=new u32[nl<<1];q=p+nl;for(int i=p[0]=1;i<nl;i++)p[i]=p[i-1]*g%mod;for(int i=0;i<nl;i++)q[i]=(u64(p[i])<<32)/mod;g=qp(g,-1);p=_p1[k]=new u32[nl<<1];q=p+nl;for(int i=p[0]=1;i<nl;i++)p[i]=p[i-1]*g%mod;for(int i=0;i<nl;i++)q[i]=(u64(p[i])<<32)/mod;}}template<class T>inline bool chkzero(const T*p,int bit){int i=0;for(;i+16<(1<<bit);i+=16){if(p[i]|p[i^1]|p[i^2]|p[i^3]|p[i^4]|p[i^5]|p[i^6]|p[i^7]|p[i^8]|p[i^9]|p[i^10]|p[i^11]|p[i^12]|p[i^13]|p[i^14]|p[i^15])return 0;}for(;i<(1<<bit);i++)if(p[i])return 0;return 1;}void ntt(u32*a,int bit,bool f=0){prep(bit);if(chkzero(a,bit))return;for(int k=bit;k-->0;){u32*_p=_p0[k],*_q=_p+(1<<k),*_a0=a,*_a1=a+(1<<k),x,y;for(int i=0;i<1<<(bit-k-1);i++,_a0+=2<<k,_a1+=2<<k)for(int j=0;j<(1<<k);++j){x=_a0[j],y=_a1[j];_a0[j]=x+y-(x+y>=modm2)*modm2,_a1[j]=fst_mul(x+modm2-y,_p[j],_q[j]);}}for(int i=0;i<(1<<bit);i++)a[i]-=(a[i]>=modm2)*modm2,a[i]-=(a[i]>=mod)*mod;if(f)butterfly(a,bit);}void intt(u32*a,int bit,bool f=0){prep(bit);if(chkzero(a,bit))return;if(f)butterfly(a,bit);for(int k=0;k<bit;k++){u32*_p=_p1[k],*_q=_p+(1<<k),*_a0=a,*_a1=a+(1<<k),x,y;for(int i=0;i<1<<(bit-k-1);i++,_a0+=2<<k,_a1+=2<<k)for(int j=0;j<(1<<k);++j){x=_a0[j]-(_a0[j]>=modm2)*modm2,y=fst_mul(_a1[j],_p[j],_q[j]);_a0[j]=x+y,_a1[j]=x+modm2-y;}}u64 iv=mod;iv<<=bit;iv=(iv-mod+1)>>bit;for(int i=0;i<(1<<bit);i++)a[i]=a[i]*iv%mod;}}using fast_number_theory_transform::ntt;using fast_number_theory_transform::intt;struct poly{vu32 f;poly(u32 x=0):f(1){f[0]=x;}poly(int x):f(1){f[0]=x+((x>>31)&mod);} poly(const vu32&_f):f(_f){}poly(const vi32&_f){f.resize(f.size());for(int i=0;i<_f.size();i++){f[i]=_f[i]+((_f[i]>>31)&mod);}}template<typename T>poly(initializer_list<T>_f):poly(vector<T>(_f)){}template<typename T>poly(T __first,T __last):poly(vector<typename iterator_traits<T>::value_type>(__first,__last)){}inline operator vu32()const{return f;}inline void swap(poly&_f){f.swap(_f.f);}inline int degree()const{return f.size()-1;}inline poly&redegree(int x){return f.resize(x+1),*this;}inline void clear(){f.resize(1);f[0]=0;}inline void shrink(){int ndeg=f.size()-1;while(ndeg>0&&f[ndeg]==0)ndeg--;f.resize(ndeg+1);}inline poly slice(int n)const{return n<=0?poly(0):(n<f.size()?poly(f.begin(),f.begin()+n+1):poly(*this).redegree(n));}inline u32&operator[](u32 x){return f[x];}inline u32 operator[](u32 x)const{return f[x];}inline u32 get(u32 x)const{return x<f.size()?f[x]:0;}friend ostream&operator<<(ostream&out,const poly&x){out<<x.f[0];for(int i=1;i<x.f.size();i++)out<<' '<<x.f[i];return out;}inline u32*data(){return f.data();}inline const u32*data()const{return f.data();}inline poly&operator+=(const poly&a){f.resize(max(f.size(),a.f.size()));for(int i=0;i<a.f.size();i++)f[i]=f[i]+a.f[i]-(f[i]+a.f[i]>=mod)*mod;return*this;}inline poly&operator-=(const poly&a){f.resize(max(f.size(),a.f.size()));for(int i=0;i<a.f.size();i++)f[i]=f[i]-a.f[i]+(f[i]<a.f[i])*mod;return*this;}inline poly operator+(const poly&a)const{return(poly(*this)+=a);}inline poly operator-(const poly&a)const{return(poly(*this)-=a);}friend inline poly operator+(u32 a,const poly&b){return(poly(b)+=a);}friend inline poly operator-(u32 a,const poly&b){return(poly(a)-=b);}inline poly operator-()const{poly _f;_f.f.resize(f.size());for(int i=0;i<_f.f.size();i++)_f.f[i]=(f[i]!=0)*mod-f[i];return _f;}inline poly&pluswith(const poly&a){for(int i=0,i_up=min(f.size(),a.f.size());i<i_up;i++)f[i]=f[i]+a.f[i]-(f[i]+a.f[i]>=mod)*mod;return*this;}inline poly plus(const poly&a)const{return(poly(*this).pluswith(a));}inline poly&minuswith(const poly&a){for(int i=0,i_up=min(f.size(),a.f.size());i<i_up;i++)f[i]=f[i]-a.f[i]+(f[i]<a.f[i])*mod;return*this;}inline poly minus(const poly&a)const{return(poly(*this).minuswith(a));}inline poly&cornerwith(const poly&a){memcpy(f.data(),a.f.data(),min(a.f.size(),f.size())*4);return*this;}inline poly corner(const poly&a)const{return poly(*this).cornerwith(a);}inline poly&operator*=(const poly&a){int n=degree(),m=a.degree();if(n<16||m<16){f.resize(n+m+1);for(int i=n+m;i>=0;i--){f[i]=1ll*f[i]*a.f[0]%mod;for(int j=max(1,i-n),j_up=min(m,i);j<=j_up;j++)f[i]=(f[i]+1ll*f[i-j]*a.f[j])%mod;}return*this;}vu32 _f(a.f);int bit=lg(n+m)+1;f.resize(1<<bit);_f.resize(1<<bit);ntt(f.data(),bit);ntt(_f.data(),bit);for(int i=0;i<(1<<bit);i++)f[i]=1ll*f[i]*_f[i]%mod;intt(f.data(),bit);f.resize(n+m+1);return*this;}inline poly operator*(const poly&a)const{return(poly(*this)*=a);}inline poly&multiplywith(const poly&_a){poly a(_a);a.shrink();int n=degree(),m=a.degree();if(n<16||m<16){for(int i=n;i>=0;i--){f[i]=1ll*f[i]*a.f[0]%mod;for(int j=max(1,i-n),j_up=min(m,i);j<=j_up;j++)f[i]=(f[i]+1ll*f[i-j]*a.f[j])%mod;}return*this;}int bit=lg(n+m)+1;f.resize(1<<bit);a.f.resize(1<<bit);ntt(f.data(),bit);ntt(a.f.data(),bit);for(int i=0;i<(1<<bit);i++)f[i]=1ll*f[i]*a.f[i]%mod;intt(f.data(),bit);f.resize(n+1);return*this;}inline poly multiply(const poly&a)const{return(poly(*this).multiplywith(a));}template<typename T> inline friend poly operator*(const poly&a, const T&b) {poly ret(a);for (int i=0;i<ret.f.size();++i) ret[i]=1ll*ret[i]*b%mod;return ret;}template<typename T>inline friend poly operator*(const T &b, const poly &a) {poly ret(a);for (int i=0;i<ret.f.size();++i) ret[i]=1ll*ret[i]*b%mod;return ret;} template<typename T> inline poly& operator *= (const T&b) {for (int i=0;i<f.size();++i) f[i]=1ll*f[i]*b%mod;return *this;} inline poly&operator<<=(int x){return f.resize(f.size()+x),memmove(f.data()+x,f.data(),4*(f.size()-x)),memset(f.data(),0,4*x),*this;}inline poly operator<<(int x)const{return(poly(*this)<<=x);}inline poly&operator>>=(int x){return x>=f.size()?(clear(),*this):(memmove(f.data(),f.data()+x,4*(f.size()-x)),f.resize(f.size()-x),*this);}inline poly operator>>(int x)const{return(poly(*this)>>=x);}inline poly&shiftindexwith(int x){return x>=f.size()?(memset(f.data(),0,4*f.size()),*this):(memmove(f.data(),f.data()+x,4*(f.size()-x)),memset(f.data(),0,4*x),*this);}inline poly shiftindex(int x)const{return(poly(*this).shiftindexwith(x));}inline poly inv()const;inline poly quo(const poly&g)const;inline poly&quowith(const poly&g){return f.size()==1?(f[0]=qp(g[0],-1,f[0]),*this):(*this=quo(g));}inline poly deri()const{int n=degree();poly res;res.redegree(n-1);for(int i=1;i<=n;i++)res[i-1]=1ll*f[i]*i%mod;return res;}inline poly intg(u32 C=0)const{int n=degree();poly res(C);res.redegree(n+1);for(int i=0;i<=n;i++)res[i+1]=1ll*ginv(i+1)*f[i]%mod;return res;}inline poly ln()const;inline poly exp()const;inline poly pow(u32 x){return(ln()*x).exp();}inline poly pow(u32 x,u32 x0){return x0!=0?((multiply(qp(f[0],-1)).ln())*x).exp()*x0:poly(0).redegree(degree());}inline poly ivsqrt()const{int nsize=f.size(),mxb=lg(f.size()-1)+1;vu32 a(1<<mxb),_f(f);_f.resize(1<<mxb);a[0]=qp(math::isqrt(f[0]),mod-2);for(int nb=0;nb<mxb;nb++){vu32 _a(a.begin(),a.begin()+(1<<nb)),_b(_f.begin(),_f.begin()+(2<<nb));_a.resize(4<<nb);_b.resize(4<<nb);ntt(_a.data(),nb+2);ntt(_b.data(),nb+2);for(int i=0;i<(4<<nb);i++)_a[i]=1ull*(mod-_a[i])*_a[i]%mod*_a[i]%mod*_b[i]%mod,_a[i]=(_a[i]+(_a[i]&1)*mod)>>1;intt(_a.data(),nb+2);memcpy(a.data()+(1<<nb),_a.data()+(1<<nb),4<<nb);}return a.resize(nsize),a;}inline poly sqrt()const{if(f.size()==1)return poly(math::isqrt(f[0]));int nsize=f.size(),mxb=lg(nsize-1)+1;vu32 a(1<<mxb),_f(f),_b;_f.resize(1<<mxb);a[0]=qp(math::isqrt(f[0]),mod-2);for(int nb=0;nb<mxb-1;nb++){vu32 _a(a.begin(),a.begin()+(1<<nb));_b=vu32(_f.begin(),_f.begin()+(2<<nb));_a.resize(4<<nb);_b.resize(4<<nb);ntt(_a.data(),nb+2);ntt(_b.data(),nb+2);for(int i=0;i<(4<<nb);i++)_a[i]=1ull*(mod-_a[i])*_a[i]%mod*_a[i]%mod*_b[i]%mod,_a[i]=(_a[i]+(_a[i]&1)*mod)>>1;intt(_a.data(),nb+2);memcpy(a.data()+(1<<nb),_a.data()+(1<<nb),4<<nb);}ntt(a.data(),mxb);vu32 _a(a);for(int i=0;i<(1<<mxb);i++)a[i]=1ll*a[i]*_b[i]%mod;intt(a.data(),mxb),memset(a.data()+(1<<(mxb-1)),0,2<<mxb);vu32 g0(a);ntt(a.data(),mxb),ntt(_f.data(),mxb);for(int i=0;i<(1<<mxb);i++)a[i]=(1ll*a[i]*a[i]+mod-_f[i])%mod*(mod-_a[i])%mod,a[i]=(a[i]+(a[i]&1)*mod)>>1;intt(a.data(),mxb);memcpy(g0.data()+(1<<(mxb-1)),a.data()+(1<<(mxb-1)),2<<mxb);return g0;}};namespace __semiconvol__{const int logbr=4,br=1<<logbr,maxdep=(maxbit-1)/logbr+1,__bf=7,bf=max(__bf,logbr-1),pbf=1<<bf;}inline poly poly::ln()const{using namespace __semiconvol__;int nsize=f.size(),mxb=lg(nsize-1)+1;math::basic_math::__prep(mxb);vu32 res(1<<mxb),__prentt[maxdep][br],_f(f);for(int i=0,k=mxb;k>bf;k-=logbr,i++){for(int j=0;j<br-1;j++){if((j<<(k-logbr))>=nsize)break;__prentt[i][j].resize(2<<(k-logbr));int nl=(j<<(k-logbr)),nr=min(((j+2)<<(k-logbr)),nsize)-nl;memcpy(__prentt[i][j].data(),_f.data()+nl,nr*4);ntt(__prentt[i][j].data(),k-logbr+1);}}function<void(int,int,int)>__div=[&res,&__prentt,&_f,&mxb,&__div](int x,int l,int r){if(r-l<=pbf){for(int i=l;i<r;i++){if(i==0)res[i]=0;else{res[i]=(1ll*i*_f[i]+mod-res[i])%mod;if(i+1<r){u64 __tmp=res[i];for(int j=i+1;j<r;j++)res[j]=(res[j]+__tmp*_f[j-i])%mod;}}}return;}int nbit=mxb-logbr*(x+1),nbr=0;vu32 __tmp[br];while(l+(nbr<<nbit)<r){__tmp[nbr].resize(2<<nbit);nbr++;}for(int i=0;i<nbr;i++){if(i!=0){intt(__tmp[i].data(),nbit+1);for(int j=0;j<(1<<nbit);j++){u32&x=res[l+(i<<nbit)+j],&y=__tmp[i][j+(1<<nbit)];x=x+y-(x+y>=mod)*mod,y=0;}}__div(x+1,l+(i<<nbit),min(l+((i+1)<<nbit),r));if(i!=nbr-1){memcpy(__tmp[i].data(),res.data()+l+(i<<nbit),4<<nbit);ntt(__tmp[i].data(),nbit+1);for(int j=i+1;j<nbr;j++)for(int k=0;k<(2<<nbit);k++)__tmp[j][k]=(__tmp[j][k]+1ll*__tmp[i][k]*__prentt[x][j-i-1][k])%mod;}}};__div(0,0,nsize);res.resize(nsize);for(int i=nsize-1;i;i--)res[i]=1ll*math::ginv(i)*res[i]%mod;return res;}inline poly poly::exp()const{using namespace __semiconvol__;int nsize=f.size(),mxb=lg(nsize-1)+1;math::basic_math::__prep(mxb);vu32 res(1<<mxb),__prentt[maxdep][br],_f(f);for(int i=0;i<nsize;i++)_f[i]=1ll*i*_f[i]%mod;for(int i=0,k=mxb;k>bf;k-=logbr,i++){for(int j=0;j<br-1;j++){if((j<<(k-logbr))>=nsize)break;__prentt[i][j].resize(2<<(k-logbr));int nl=(j<<(k-logbr)),nr=min(((j+2)<<(k-logbr)),nsize)-nl;memcpy(__prentt[i][j].data(),_f.data()+nl,nr*4);ntt(__prentt[i][j].data(),k-logbr+1);}}function<void(int,int,int)>__div=[&res,&__prentt,&_f,&mxb,&__div](int x,int l,int r){if(r-l<=pbf){for(int i=l;i<r;i++){res[i]=i==0?1:1ll*math::ginv(i)*res[i]%mod;if(i+1<r){u64 __tmp=res[i];for(int j=i+1;j<r;j++)res[j]=(res[j]+__tmp*_f[j-i])%mod;}}return;}int nbit=mxb-logbr*(x+1),nbr=0;vu32 __tmp[br];while(l+(nbr<<nbit)<r){__tmp[nbr].resize(2<<nbit);nbr++;}for(int i=0;i<nbr;i++){if(i!=0){intt(__tmp[i].data(),nbit+1);for(int j=0;j<(1<<nbit);j++){u32&x=res[l+(i<<nbit)+j],&y=__tmp[i][j+(1<<nbit)];x=x+y-(x+y>=mod)*mod,y=0;}}__div(x+1,l+(i<<nbit),min(l+((i+1)<<nbit),r));if(i!=nbr-1){memcpy(__tmp[i].data(),res.data()+l+(i<<nbit),4<<nbit);ntt(__tmp[i].data(),nbit+1);for(int j=i+1;j<nbr;j++)for(int k=0;k<(2<<nbit);k++)__tmp[j][k]=(__tmp[j][k]+1ll*__tmp[i][k]*__prentt[x][j-i-1][k])%mod;}}};__div(0,0,nsize);return res.resize(nsize),res;}inline poly poly::inv()const{using namespace __semiconvol__;int nsize=f.size(),mxb=lg(nsize-1)+1;vu32 res(1<<mxb),__prentt[maxdep][br],_f(f);u32 ivf0=qp(f[0],-1);_f[0]=0;for(int i=0,k=mxb;k>bf;k-=logbr,i++){for(int j=0;j<br-1;j++){if((j<<(k-logbr))>=nsize)break;__prentt[i][j].resize(2<<(k-logbr));int nl=(j<<(k-logbr)),nr=min(((j+2)<<(k-logbr)),nsize)-nl;memcpy(__prentt[i][j].data(),_f.data()+nl,nr*4);ntt(__prentt[i][j].data(),k-logbr+1);}}function<void(int,int,int)>__div=[&res,&__prentt,&_f,&mxb,&__div,&ivf0](int x,int l,int r){if(r-l<=pbf){for(int i=l;i<r;i++){res[i]=i==0?ivf0:1ll*ivf0*(mod-res[i])%mod;if(i+1<r){u64 __tmp=res[i];for(int j=i+1;j<r;j++)res[j]=(res[j]+__tmp*_f[j-i])%mod;}}return;}int nbit=mxb-logbr*(x+1),nbr=0;vu32 __tmp[br];while(l+(nbr<<nbit)<r){__tmp[nbr].resize(2<<nbit);nbr++;}for(int i=0;i<nbr;i++){if(i!=0){intt(__tmp[i].data(),nbit+1);for(int j=0;j<(1<<nbit);j++){u32&x=res[l+(i<<nbit)+j],&y=__tmp[i][j+(1<<nbit)];x=x+y-(x+y>=mod)*mod,y=0;}}__div(x+1,l+(i<<nbit),min(l+((i+1)<<nbit),r));if(i!=nbr-1){memcpy(__tmp[i].data(),res.data()+l+(i<<nbit),4<<nbit);ntt(__tmp[i].data(),nbit+1);for(int j=i+1;j<nbr;j++)for(int k=0;k<(2<<nbit);k++)__tmp[j][k]=(__tmp[j][k]+1ll*__tmp[i][k]*__prentt[x][j-i-1][k])%mod;}}};__div(0,0,nsize);return res.resize(nsize),res;}inline poly poly::quo(const poly&g)const{using namespace __semiconvol__;int nsize=f.size(),mxb=lg(nsize-1)+1;vu32 res(1<<mxb),__prentt[maxdep][br],_f(g.f);u32 ivf0=qp(_f[0],-1);_f[0]=0;_f.resize(nsize);for(int i=0,k=mxb;k>bf;k-=logbr,i++){for(int j=0;j<br-1;j++){if((j<<(k-logbr))>=nsize)break;__prentt[i][j].resize(2<<(k-logbr));int nl=(j<<(k-logbr)),nr=min(((j+2)<<(k-logbr)),nsize)-nl;memcpy(__prentt[i][j].data(),_f.data()+nl,nr*4);ntt(__prentt[i][j].data(),k-logbr+1);}}function<void(int,int,int)>__div=[=,&res,&__prentt,&_f,&mxb,&__div,&ivf0](int x,int l,int r){if(r-l<=pbf){for(int i=l;i<r;i++){res[i]=1ll*ivf0*(i==0?f[0]:f[i]+mod-res[i])%mod;if(i+1<r){u64 __tmp=res[i];for(int j=i+1;j<r;j++)res[j]=(res[j]+__tmp*_f[j-i])%mod;}}return;}int nbit=mxb-logbr*(x+1),nbr=0;vu32 __tmp[br];while(l+(nbr<<nbit)<r){__tmp[nbr].resize(2<<nbit);nbr++;}for(int i=0;i<nbr;i++){if(i!=0){intt(__tmp[i].data(),nbit+1);for(int j=0;j<(1<<nbit);j++){u32&x=res[l+(i<<nbit)+j],&y=__tmp[i][j+(1<<nbit)];x=x+y-(x+y>=mod)*mod,y=0;}}__div(x+1,l+(i<<nbit),min(l+((i+1)<<nbit),r));if(i!=nbr-1){memcpy(__tmp[i].data(),res.data()+l+(i<<nbit),4<<nbit);ntt(__tmp[i].data(),nbit+1);for(int j=i+1;j<nbr;j++)for(int k=0;k<(2<<nbit);k++)__tmp[j][k]=(__tmp[j][k]+1ll*__tmp[i][k]*__prentt[x][j-i-1][k])%mod;}}};__div(0,0,nsize);return res.resize(nsize),res;}}using math::qp;using polynormial::poly;
} using namespace __POLY__;
sa and sth:
/usr/bin/time -f "%es, %MKB" ./std
const int N = 1e6 + 10;
char ch[N];
int n, sa[N], rk[N];
void getsa(char ch[], int sa[], int rk[]) {
int m = 127;
static int cnt[N], rk2[N], key[N], id[N];
memset(cnt+1, 0, m << 2);
rep(i,1,n) rk[i] = ch[i], cnt[rk[i]]++;
rep(i,1,m) cnt[i] += cnt[i-1];
pre(i,n,1) sa[cnt[rk[i]] --] = i;
for (int w = 1; ; w <<= 1) {
int p = 0;
for (register int i = n; i > n - w; -- i) id[++p] = i;
rep(i,1,n) if (sa[i] > w) id[++p] = sa[i] - w;
memset(cnt + 1, 0, m << 2);
rep(i,1,n) key[i] = rk[id[i]], cnt[key[i]]++;
rep(i,1,m) cnt[i] += cnt[i-1];
pre(i,n,1) sa[cnt[key[i]] --] = id[i];
memcpy(rk2+1, rk+1, n << 2);
p = 0;
rep(i,1,n) rk[sa[i]] = (
rk2[sa[i]] == rk2[sa[i-1]] and
rk2[sa[i] + w] == rk2[sa[i-1] + w]
) ? p : ++p;
if (p == n) { rep(i,1,n) sa[rk[i]] = i; break; }
m = p;
}
}
void getheight() {
for (int i = 1, k = 0; i <= n; i++) {
if (rk[i] == 0) continue;
if (k) k--;
while (s[i + k] == s[sa[rk[i] - 1] + k]) k++;
height[rk[i]] = k;
}
}
typedef long long ll; typedef __int128 lll;
struct FastMod { int m; ll b; void init(int _m) { m = _m; b = ((lll)1<<64) / m; } int operator() (ll a) {ll q = ((lll)a * b) >> 64; a -= q * m; if (a >= m) a -= m; return a; } } Mod;
int add(ll a, int b) { return (a += b) >= mod ? a - mod : a; } int mul(int a, int b) { return Mod(1ll * a * b); } template <typename ...Args> int mul(int a, Args ...b) { return mul(a, mul(b...)); }
#pragma GCC target("sse,sse2,sse3,sse4.1,sse4.2,popcnt,abm,mmx,avx")
#pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize("Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2,-ffast-math,-fsched-spec,unroll-loops,-falign-jumps,-falign-loops,-falign-labels,-fdevirtualize,-fcaller-saves,-fcrossjumping,-fthread-jumps,-funroll-loops,-fwhole-program,-freorder-blocks,-fschedule-insns,inline-functions,-ftree-tail-merge,-fschedule-insns2,-fstrict-aliasing,-fstrict-overflow,-falign-functions,-fcse-skip-blocks,-fcse-follow-jumps,-fsched-interblock,-fpartial-inlining,no-stack-protector,-freorder-functions,-findirect-inlining,-fhoist-adjacent-loads,-frerun-cse-after-loop,inline-small-functions,-finline-small-functions,-ftree-switch-conversion,-foptimize-sibling-calls,-fexpensive-optimizations,-funsafe-loop-optimizations,inline-functions-called-once,-fdelete-null-pointer-checks")