代码

#include <bits/stdc++.h>
using namespace std;
const int Mod = 998244353, MAXN = 3e6 + 7;
typedef long long ll;
inline ll Pow ( ll bs, int t ) { ll rt = 1; for ( ; t; t >>= 1, bs = bs * bs % Mod ) if ( t & 1 ) rt = rt * bs % Mod; return rt; }
inline int Mop ( int na ) { return na >= Mod ? na - Mod : na; }

int pos[MAXN];
void Pre ( int sz )
{
	int lm = 0;
	for ( ; ( 1 << lm ) < sz; ++lm );
	for ( int i = 0; i < sz; ++i ) { pos[i] = pos[i >> 1] >> 1; if ( i & 1 ) pos[i] |= ( 1 << lm - 1 ); }
}

ll w[MAXN];
void Gao ( ll *t, int sz, int tp )
{
	for ( int i = 0; i < sz; ++i ) if ( pos[i] < i ) swap ( t[i], t[pos[i]] );
	for ( int nl = 2; nl <= sz; nl <<= 1 )
	{
		int hl = nl >> 1;
		w[0] = 1, w[1] = Pow ( 3, ( Mod - 1 ) / nl );
		if ( tp == -1 ) w[1] = Pow ( w[1], Mod - 2 );
		for ( int i = 2; i < hl; ++i ) w[i] = w[i - 1] * w[1] % Mod;
		for ( int sp = 0; sp < sz; sp += nl )
			for ( ll *l = t + sp, *r = t + sp + hl, *lm = t + sp + nl, *nw = w; r != lm; ++l, ++r, ++nw )
			{
				ll temp = *r * *nw % Mod;
				*r = Mop ( *l + Mod - temp ), *l = Mop ( *l + temp );
			}
	}
	if ( tp == -1 ) { ll rv = Pow ( sz, Mod - 2 ); for ( int i = 0; i < sz; ++i ) t[i] = t[i] * rv % Mod; }
}

ll aa[MAXN], bb[MAXN];
void poly_multiply ( unsigned *a, int n, unsigned *b, int m, unsigned *c )
{
	int ms = 1, ss = n + m + 1;
	for ( int i = 0; i <= n; ++i ) aa[i] = a[i];
	for ( int i = 0; i <= m; ++i ) bb[i] = b[i];
	for ( ; ms < ss; ms <<= 1 );
	Pre ( ms ), Gao ( aa, ms, 1 ), Gao ( bb, ms, 1 );
	for ( int i = 0; i < ms; ++i ) aa[i] = aa[i] * bb[i] % Mod;
	Gao ( aa, ms, -1 );
	for ( int i = 0; i < ss; ++i ) c[i] = aa[i];
}

评测结果