提交记录 7727


用户 题目 状态 得分 用时 内存 语言 代码长度
nansns 1002i. 【模板题】多项式乘法 Accepted 100 62.398 ms 7728 KB C++ 1.61 KB
提交时间 评测时间
2019-01-25 09:35:17 2020-08-01 01:07:46
#include <bits/stdc++.h>
#define Pb push_back
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 3e5 + 7, Mod = 998244353;
inline int R() { int rt; scanf ( "%d", &rt ); return rt; }
ll Pow ( ll bs, int t ) { int 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 a[MAXN], b[MAXN], 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 ( int i = sp; i < sp + hl; ++i )
			{
				ll temp = t[i + hl] * w[i - sp] % Mod;
				t[i + hl] = Mop ( t[i] + Mod - temp );
				t[i] = Mop ( t[i] + temp );
			}
	}
	if ( tp == -1 ) { ll rv = Pow ( sz, Mod - 2 ); for ( int i = 0; i < sz; ++i ) t[i] = t[i] * rv % Mod; }
}

int main()
{
	int n = R(), m = R(), ms = 1;
	for ( ; ms < n + m + 1; ms <<= 1 );
	for ( int i = 0; i <= n; ++i ) a[i] = R();
	for ( int i = 0; i <= m; ++i ) b[i] = R();
	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 < n + m + 1; ++i ) printf ( "%lld ", a[i] );
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #137.42 us52 KBAcceptedScore: 0

Subtask #1 Testcase #261.373 ms7 MB + 480 KBAcceptedScore: 100

Subtask #1 Testcase #327.979 ms3 MB + 332 KBAcceptedScore: 0

Subtask #1 Testcase #428.001 ms3 MB + 320 KBAcceptedScore: 0

Subtask #1 Testcase #540.38 us52 KBAcceptedScore: 0

Subtask #1 Testcase #637.95 us52 KBAcceptedScore: 0

Subtask #1 Testcase #737.86 us52 KBAcceptedScore: 0

Subtask #1 Testcase #855.478 ms7 MB + 212 KBAcceptedScore: 0

Subtask #1 Testcase #955.437 ms7 MB + 212 KBAcceptedScore: 0

Subtask #1 Testcase #1049.651 ms6 MB + 968 KBAcceptedScore: 0

Subtask #1 Testcase #1161.677 ms7 MB + 560 KBAcceptedScore: 0

Subtask #1 Testcase #1262.398 ms6 MB + 440 KBAcceptedScore: 0

Subtask #1 Testcase #1336.36 us52 KBAcceptedScore: 0


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