結果
問題 | No.931 Multiplicative Convolution |
ユーザー |
👑 ![]() |
提出日時 | 2019-11-23 01:58:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 7,746 bytes |
コンパイル時間 | 1,762 ms |
コンパイル使用メモリ | 136,536 KB |
最終ジャッジ日時 | 2025-01-08 05:26:04 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 TLE * 1 |
ソースコード
#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;}