結果

問題 No.931 Multiplicative Convolution
ユーザー goodbaton
提出日時 2020-08-10 16:39:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 210 ms / 2,000 ms
コード長 4,089 bytes
コンパイル時間 1,170 ms
コンパイル使用メモリ 106,548 KB
実行使用メモリ 8,576 KB
最終ジャッジ日時 2024-10-07 22:35:00
合計ジャッジ時間 4,446 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cassert>
#include <functional>
typedef long long ll;
using namespace std;
#ifndef LOCAL
#define debug(...) ;
#else
#define debug(...) cerr << __LINE__ << " : " << #__VA_ARGS__ << " = " << _tostr(__VA_ARGS__) << endl;
template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v);
template<typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
out << "{" << p.first << ", " << p.second << "}";
return out;
}
template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
out << '{';
for (const T &item : v) out << item << ", ";
out << "\b\b}";
return out;
}
void _tostr_rec(ostringstream &oss) {
oss << "\b\b \b";
}
template<typename Head, typename... Tail>
void _tostr_rec(ostringstream &oss, Head &&head, Tail &&... tail) {
oss << head << ", ";
_tostr_rec(oss, forward<Tail>(tail)...);
}
template<typename... T>
string _tostr(T &&... args) {
ostringstream oss;
int size = sizeof...(args);
if (size > 1) oss << "{";
_tostr_rec(oss, forward<T>(args)...);
if (size > 1) oss << "}";
return oss.str();
}
#endif
// #define mod 1000000007 //1e9+7(prime number)
#define mod 998244353
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010
ll power(ll k, ll n, int M) {
ll res = 1;
while (n > 0) {
if (n & 1) res = res * k % M;
k = k * k % M;
n /= 2;
}
return res;
}
ll getPrimitiveRoot(ll P) {
if (P == 2) return 1;
// assert(isPrime(P) && P >= 3);
ll p = P - 1;
vector<ll> a;
for (int i = 2; i * i <= p; i++) {
if (p % i == 0) a.push_back(i);
while (p % i == 0) p /= i;
}
if (p > 1) a.push_back(p);
while (1) {
bool ok = true;
ll r = rand() % (P - 2) + 2;
for (auto q : a)
ok &= power(r, (P - 1) / q, P) != 1;
if (ok) return r;
}
}
/* Number Theoretic Transform */
namespace NTT {
void DFT(int m, int root, vector<int> &a, bool rev = false) {
int N = a.size();
for (int i = 0, j = 1; j + 1 < N; j++) {
for (int k = N >> 1; k > (i ^= k); k >>= 1)
;
if (i > j) swap(a[i], a[j]);
}
int g = power(root, (m - 1) / N, m);
if (rev) g = power(g, m - 2, m);
for (int i = 1; i < N; i *= 2) {
int base = power(g, N / i / 2, m);
ll w = 1;
for (int j = 0; j < i; j++) {
for (int k = 0; k < N; k += i * 2) {
int s = a[j + k], t = a[j + k + i] * w % m;
a[j + k + 0] = (s + t) % m;
a[j + k + i] = (s - t + m) % m;
}
w = w * base % m;
}
}
if (rev) {
ll tmp = power(N, m - 2, m);
for (int &v : a) v = v * tmp % m;
}
}
// (469762049, 3), (924844033, 5), (998244353, 3), (1012924417, 5)
vector<int> conv(int _mod, int root, const vector<int> &a, const vector<int> &b) {
int s = 1, t = a.size() + b.size() - 1;
while (s < t) s *= 2;
vector<int> F(s), G(s);
for (int i = 0; i < (int)a.size(); i++) F[i] = a[i];
for (int i = 0; i < (int)b.size(); i++) G[i] = b[i];
DFT(_mod, root, F);
DFT(_mod, root, G);
for (int i = 0; i < s; i++) F[i] = (ll)F[i] * G[i] % _mod;
DFT(_mod, root, F, true);
return F;
}
};
int main() {
int P, A[SIZE], B[SIZE];
ll ans[SIZE] = {};
scanf("%d", &P);
for (int i = 1; i < P; i++) scanf("%d", A + i);
for (int i = 1; i < P; i++) scanf("%d", B + i);
ll R = getPrimitiveRoot(P);
vector<int> v1(P), v2(P);
ll t = 1;
for (int i = 0; i < P - 1; i++) {
v1[i] = A[t];
v2[i] = B[t];
t = t * R % P;
}
auto v = NTT::conv(mod, 3, v1, v2);
t = 1;
for (auto p : v) {
ans[t] += p;
t = t * R % P;
}
for (int i = 1; i < P; i++) {
printf("%lld%c", ans[i] % mod, " \n"[i + 1 == P]);
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0