結果
| 問題 | No.931 Multiplicative Convolution |
| ユーザー |
👑  emthrm
|
| 提出日時 | 2019-11-23 01:58:39 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,746 bytes |
| コンパイル時間 | 1,825 ms |
| コンパイル使用メモリ | 142,596 KB |
| 実行使用メモリ | 10,240 KB |
| 最終ジャッジ日時 | 2024-10-11 06:44:51 |
| 合計ジャッジ時間 | 9,211 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,248 KB |
| testcase_02 | AC | 2 ms
5,248 KB |
| testcase_03 | AC | 2 ms
5,248 KB |
| testcase_04 | AC | 2 ms
5,248 KB |
| testcase_05 | AC | 2 ms
5,248 KB |
| testcase_06 | AC | 5 ms
5,248 KB |
| testcase_07 | AC | 55 ms
5,248 KB |
| testcase_08 | AC | 451 ms
9,856 KB |
| testcase_09 | AC | 246 ms
9,088 KB |
| testcase_10 | AC | 628 ms
10,240 KB |
| testcase_11 | AC | 364 ms
9,600 KB |
| testcase_12 | AC | 174 ms
6,784 KB |
| testcase_13 | TLE | - |
| testcase_14 | AC | 835 ms
9,856 KB |
| testcase_15 | AC | 421 ms
9,984 KB |
| testcase_16 | AC | 474 ms
9,728 KB |
ソースコード
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
// const int MOD = 1000000007;
const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
// const int dy[] = {1, 1, 0, -1, -1, -1, 0, 1},
// dx[] = {0, -1, -1, -1, 0, 1, 1, 1};
struct IOSetup {
IOSetup() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(20);
cerr << fixed << setprecision(10);
}
} iosetup;
/*-------------------------------------------------*/
int mod = MOD;
struct ModInt {
unsigned val;
ModInt(): val(0) {}
ModInt(long long x) : val(x >= 0 ? x % mod : x % mod + mod) {}
ModInt pow(long long exponent) {
ModInt tmp = *this, res = 1;
while (exponent > 0) {
if (exponent & 1) res *= tmp;
tmp *= tmp;
exponent >>= 1;
}
return res;
}
ModInt &operator+=(const ModInt &rhs) { if((val += rhs.val) >= mod) val -= mod; return *this; }
ModInt &operator-=(const ModInt &rhs) { if((val += mod - rhs.val) >= mod) val -= mod; return *this; }
ModInt &operator*=(const ModInt &rhs) { val = static_cast<unsigned long long>(val) * rhs.val % mod; return *this; }
ModInt &operator/=(const ModInt &rhs) { return *this *= rhs.inv(); }
bool operator==(const ModInt &rhs) const { return val == rhs.val; }
bool operator!=(const ModInt &rhs) const { return val != rhs.val; }
bool operator<(const ModInt &rhs) const { return val < rhs.val; }
bool operator<=(const ModInt &rhs) const { return val <= rhs.val; }
bool operator>(const ModInt &rhs) const { return val > rhs.val; }
bool operator>=(const ModInt &rhs) const { return val >= rhs.val; }
ModInt operator-() const { return ModInt(val ? mod - val : 0); }
ModInt operator+(const ModInt &rhs) const { return ModInt(*this) += rhs; }
ModInt operator-(const ModInt &rhs) const { return ModInt(*this) -= rhs; }
ModInt operator*(const ModInt &rhs) const { return ModInt(*this) *= rhs; }
ModInt operator/(const ModInt &rhs) const { return ModInt(*this) /= rhs; }
friend ostream &operator<<(ostream &os, const ModInt &rhs) { return os << rhs.val; }
friend istream &operator>>(istream &is, ModInt &rhs) { long long x; is >> x; rhs = ModInt(x); return is; }
private:
ModInt inv() const {
// if (__gcd(val, mod) != 1) assert(false);
unsigned a = val, b = mod; int x = 1, y = 0;
while (b) {
unsigned tmp = a / b;
swap(a -= tmp * b, b);
swap(x -= tmp * y, y);
}
return ModInt(x);
}
};
int abs(const ModInt &x) { return x.val; }
struct Combinatorics {
int val;
vector<ModInt> fact, fact_inv, inv;
Combinatorics(int val = 10000000) : val(val), fact(val + 1), fact_inv(val + 1), inv(val + 1) {
fact[0] = 1;
FOR(i, 1, val + 1) fact[i] = fact[i - 1] * i;
fact_inv[val] = ModInt(1) / fact[val];
for (int i = val; i > 0; --i) fact_inv[i - 1] = fact_inv[i] * i;
FOR(i, 1, val + 1) inv[i] = fact[i - 1] * fact_inv[i];
}
ModInt nCk(int n, int k) {
if (n < 0 || n < k || k < 0) return ModInt(0);
// assert(n <= val && k <= val);
return fact[n] * fact_inv[k] * fact_inv[n - k];
}
ModInt nPk(int n, int k) {
if (n < 0 || n < k || k < 0) return ModInt(0);
// assert(n <= val);
return fact[n] * fact_inv[n - k];
}
ModInt nHk(int n, int k) {
if (n < 0 || k < 0) return ModInt(0);
return (k == 0 ? ModInt(1) : nCk(n + k - 1, k));
}
};
struct NTT {
NTT(int mod_) {
mod = mod_;
REP(i, 23 + 1) {
// if (i == 23) assert(false);
if (primes[i][0] == mod) {
n_max = 1 << primes[i][2];
root = ModInt(primes[i][1]).pow((mod - 1) >> primes[i][2]);
break;
}
}
}
void sub_dft(vector<ModInt> &a) {
int n = a.size();
// assert(__builtin_popcount(n) == 1);
calc(n);
int shift = __builtin_ctz(butterfly.size()) - __builtin_ctz(n);
REP(i, n) {
int j = butterfly[i] >> shift;
if (i < j) swap(a[i], a[j]);
}
for (int block = 1; block < n; block <<= 1) {
int den = __builtin_ctz(block);
for (int i = 0; i < n; i += (block << 1)) REP(j, block) {
ModInt tmp = a[i + j + block] * omega[den][j];
a[i + j + block] = a[i + j] - tmp;
a[i + j] += tmp;
}
}
}
template <typename T>
vector<ModInt> dft(const vector<T> &a) {
int sz = a.size(), lg = 1;
while ((1 << lg) < sz) ++lg;
vector<ModInt> A(1 << lg, 0);
REP(i, sz) A[i] = a[i];
sub_dft(A);
return A;
}
void idft(vector<ModInt> &a) {
int n = a.size();
// assert(__builtin_popcount(n) == 1);
sub_dft(a);
reverse(a.begin() + 1, a.end());
ModInt inv_n = ModInt(1) / n;
REP(i, n) a[i] *= inv_n;
}
template <typename T>
vector<ModInt> convolution(const vector<T> &a, const vector<T> &b) {
int a_sz = a.size(), b_sz = b.size(), sz = a_sz + b_sz - 1, lg = 1;
while ((1 << lg) < sz) ++lg;
int n = 1 << lg;
vector<ModInt> A(n, 0), B(n, 0);
REP(i, a_sz) A[i] = a[i];
REP(i, b_sz) B[i] = b[i];
sub_dft(A);
sub_dft(B);
REP(i, n) A[i] *= B[i];
idft(A);
A.resize(sz);
return A;
}
private:
const int primes[23][3] = {
{16957441, 329, 14},
{17006593, 26, 15},
{19529729, 770, 17},
{167772161, 3, 25},
{469762049, 3, 26},
{645922817, 3, 23},
{897581057, 3, 23},
{924844033, 5, 21},
{935329793, 3, 22},
{943718401, 7, 22},
{950009857, 7, 21},
{962592769, 7, 21},
{975175681, 17, 21},
{976224257, 3, 20},
{985661441, 3, 22},
{998244353, 3, 23},
{1004535809, 3, 21},
{1007681537, 3, 20},
{1012924417, 5, 21},
{1045430273, 3, 20},
{1051721729, 6, 20},
{1053818881, 7, 20},
{1224736769, 3, 24}
};
int n_max;
ModInt root;
vector<int> butterfly{0};
vector<vector<ModInt> > omega{{1}};
void calc(int n) {
int prev_n = butterfly.size();
if (n <= prev_n) return;
// assert(n <= n_max);
butterfly.resize(n);
int prev_lg = omega.size(), lg = __builtin_ctz(n);
FOR(i, 1, prev_n) butterfly[i] <<= lg - prev_lg;
FOR(i, prev_n, n) butterfly[i] = (butterfly[i >> 1] >> 1) | ((i & 1) << (lg - 1));
omega.resize(lg);
FOR(i, prev_lg, lg) {
omega[i].resize(1 << i);
ModInt tmp = root.pow((mod - 1) / (1 << (i + 1)));
REP(j, 1 << (i - 1)) {
omega[i][j << 1] = omega[i - 1][j];
omega[i][(j << 1) + 1] = omega[i - 1][j] * tmp;
}
}
}
};
int main() {
int p; cin >> p;
mod = p;
int root = 2;
while (true) {
set<ModInt> st;
FOR(i, 1, p) st.emplace(ModInt(root).pow(i));
if (st.size() == p - 1) break;
++root;
}
vector<int> a(p, 0), b(p, 0);
FOR(i, 1, p) cin >> a[i];
FOR(i, 1, p) cin >> b[i];
vector<int> A(p - 1, 0), B(p - 1, 0);
REP(i, p - 1) {
A[i] = a[ModInt(root).pow(i).val];
B[i] = b[ModInt(root).pow(i).val];
}
NTT ntt(MOD);
vector<ModInt> C = ntt.convolution(A, B);
FOR(i, p - 1, C.size()) C[i % (p - 1)] += C[i];
mod = p;
vector<ModInt> ans(p, 0);
REP(i, p - 1) ans[ModInt(root).pow(i).val] = C[i];
FOR(i, 1, p) cout << ans[i] << (i + 1 == p ? '\n' : ' ');
return 0;
}