代码

#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 ) / sz );
		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 ( int i = sp; i < sp + hl; ++i )
			{
				ll tp = t[i + hl] * w[i - sp] % Mod;
				t[i + hl] = Mop ( t[i] + Mod - tp );
				t[i] = Mop ( t[i] + tp );
			}
	}
	if ( tp == -1 ) { ll rv = Pow ( sz, Mod - 2 ); for ( int i = 0; i < sz; ++i ) t[i] = t[i] * rv % Mod; }
}

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

评测结果