結果
| 問題 | No.1574 Swap and Repaint |
| ユーザー |
 KoD
|
| 提出日時 | 2021-06-20 17:26:14 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 17,334 bytes |
| コンパイル時間 | 30,452 ms |
| コンパイル使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2025-01-22 10:38:07 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
コンパイルが30秒の制限時間を超えました
ソースコード
#include <bits/extc++.h>#include <unistd.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifusing ll = long long;using ld = long double;using ull = long long;#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++(i))#define ALL(x) begin(x), end(x)#define all(s) (s).begin(), (s).end()#define rep2(i, m, n) for (int i = (m); i < (n); ++i)#define rep(i, n) rep2(i, 0, n)#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)#define drep(i, n) drep2(i, n, 0)#define rever(vec) reverse(vec.begin(), vec.end())#define sor(vec) sort(vec.begin(), vec.end())#define fi first#define se second#define P pair<ll, ll>#define REP(i, n) for (int i = 0; i < (n); ++i)#define in scanner.read_int()const ll mod = 998244353;// const ll mod = 1000000007;const ll inf = 2000000000000000000ll;static const long double pi = 3.141592653589793;template <class T> void vcin(vector<T>& n) {for (int i = 0; i < int(n.size()); i++) cin >> n[i];}template <class T> void vcout(vector<T>& n) {for (int i = 0; i < int(n.size()); i++) {cout << n[i] << " ";}cout << endl;}void YesNo(bool a) {if (a) {cout << "Yes" << endl;} else {cout << "No" << endl;}}void YESNO(bool a) {if (a) {cout << "YES" << endl;} else {cout << "NO" << endl;}}template <class T, class U> void chmax(T& t, const U& u) {if (t < u) t = u;}template <class T, class U> void chmin(T& t, const U& u) {if (t > u) t = u;}template <class T> void ifmin(T t, T u) {if (t > u) {cout << -1 << endl;} else {cout << t << endl;}}template <class T> void ifmax(T t, T u) {if (t > u) {cout << -1 << endl;} else {cout << t << endl;}}template <typename T, typename... Args> auto make_vector(T x, int arg, Args... args) {if constexpr (sizeof...(args) == 0)return vector<T>(arg, x);elsereturn vector(arg, make_vector<T>(x, args...));}ll modPow(ll a, ll n, ll mod) {ll ret = 1;ll p = a % mod;while (n) {if (n & 1) ret = ret * p % mod;p = p * p % mod;n >>= 1;}return ret;}void gbjsmzmfuuvdf() {ios::sync_with_stdio(false);std::cin.tie(nullptr);cout << fixed << setprecision(20);}class Scanner {vector<char> buffer;ssize_t n_written;ssize_t n_read;public:Scanner() : buffer(1024 * 1024) { do_read(); }int64_t read_int() {int64_t ret = 0, sgn = 1;int ch = current_char();while (isspace(ch)) {ch = next_char();}if (ch == '-') {sgn = -1;ch = next_char();}for (; isdigit(ch); ch = next_char()) ret = (ret * 10) + (ch - '0');return sgn * ret;}private:void do_read() {ssize_t r = read(0, &buffer[0], buffer.size());if (r < 0) {throw runtime_error(strerror(errno));}n_written = r;n_read = 0;}inline int next_char() {++n_read;if (n_read == n_written) {do_read();}return current_char();}inline int current_char() { return (n_read == n_written) ? EOF : buffer[n_read]; }};using mint = modint998244353;struct S {mint value;int size;};using F = mint;S op(S a, S b) { return {a.value + b.value, a.size + b.size}; }S e() { return {mint(0), 1}; }S mapping(F f, S x) { return {x.value + x.size * f, x.size}; }F composition(F f, F g) { return f + g; }F id() { return mint(0); }mint k[200100];void com() {k[0] = 1;for (int i = 1; i < 200100; i++) {k[i] = k[i - 1] * i;}}enum Mode {FAST = 1,NAIVE = -1,};template <class T, Mode mode = FAST> struct FormalPowerSeries : std::vector<T> {using std::vector<T>::vector;using std::vector<T>::size;using std::vector<T>::resize;using F = FormalPowerSeries;F& operator+=(const F& g) {for (int i = 0; i < int(min((*this).size(), g.size())); i++) {(*this)[i] += g[i];}return *this;}F& operator+=(const T& t) {assert(int((*this).size()));(*this)[0] += t;return *this;}F& operator-=(const F& g) {for (int i = 0; i < int(min((*this).size(), g.size())); i++) {(*this)[i] -= g[i];}return *this;}F& operator-=(const T& t) {assert(int((*this).size()));(*this)[0] -= t;return *this;}F& operator*=(const T& g) {for (int i = 0; i < int((*this).size()); i++) {(*this)[i] *= g;}return *this;}F& operator/=(const T& g) {T div = g.inv();for (int i = 0; i < int((*this).size()); i++) {(*this)[i] *= div;}return *this;}F& operator<<=(const int d) {int n = (*this).size();(*this).insert((*this).begin(), d, 0);(*this).resize(n);return *this;}F& operator>>=(const int d) {int n = (*this).size();(*this).erase((*this).begin(), (*this).begin() + min(n, d));(*this).resize(n);return *this;}F& operator=(const std::vector<T>& v) {int n = (*this).size();for (int i = 0; i < n; ++i) (*this)[i] = v[i];return *this;}F operator-() const {F ret = *this;return ret * -1;}F& operator*=(const F& g) {if (mode == FAST) {int n = (*this).size();auto tmp = atcoder::convolution(*this, g);for (int i = 0; i < n; ++i) {(*this)[i] = tmp[i];}return *this;} else {int n = (*this).size(), m = g.size();for (int i = n - 1; i >= 0; --i) {(*this)[i] *= g[0];for (int j = 1; j < std::min(i + 1, m); j++) (*this)[i] += (*this)[i - j] * g[j];}return *this;}}F& operator/=(const F& g) {if (mode == FAST) {int n = (*this).size();(*this) = atcoder::convolution(*this, g.inv());return *this;} else {assert(g[0] != T(0));T ig0 = g[0].inv();int n = (*this).size(), m = g.size();for (int i = 0; i < n; ++i) {for (int j = 1; j < std::min(i + 1, m); ++j) (*this)[i] -= (*this)[i - j] * g[j];(*this)[i] *= ig0;}return *this;}}F& operator%=(const F& g) { return *this -= *this / g * g; }F operator*(const T& g) const { return F(*this) *= g; }F operator-(const T& g) const { return F(*this) -= g; }F operator*(const F& g) const { return F(*this) *= g; }F operator-(const F& g) const { return F(*this) -= g; }F operator+(const F& g) const { return F(*this) += g; }F operator/(const F& g) const { return F(*this) /= g; }F operator%(const F& g) const { return F(*this) %= g; }F operator<<(const int d) const { return F(*this) <<= d; }F operator>>(const int d) const { return F(*this) >>= d; }void onemul(const int d, const T c) {int n = (*this).size();for (int i = n - d - 1; i >= 0; i--) {(*this)[i + d] += (*this)[i] * c;}}void onediv(const int d, const T c) {int n = (*this).size();for (int i = 0; i < n - d; i++) {(*this)[i + d] -= (*this)[i] * c;}}T eval(const T& t) const {int n = (*this).size();T res = 0, tmp = 1;for (int i = 0; i < n; ++i) {res += (*this)[i] * tmp, tmp *= t;}return res;}F inv(int deg = -1) const {int n = (*this).size();assert(mode == FAST and n and (*this)[0] != 0);if (deg == -1) deg = n;assert(deg > 0);F res{(*this)[0].inv()};while (int(res.size()) < deg) {int m = res.size();F f((*this).begin(), (*this).begin() + std::min(n, m * 2)), r(res);f.resize(m * 2), atcoder::internal::butterfly(f);r.resize(m * 2), atcoder::internal::butterfly(r);for (int i = 0; i < m * 2; ++i) f[i] *= r[i];atcoder::internal::butterfly_inv(f);f.erase(f.begin(), f.begin() + m);f.resize(m * 2), atcoder::internal::butterfly(f);for (int i = 0; i < m * 2; ++i) f[i] *= r[i];atcoder::internal::butterfly_inv(f);T iz = T(m * 2).inv();iz *= -iz;for (int i = 0; i < m; ++i) f[i] *= iz;res.insert(res.end(), f.begin(), f.begin() + m);}res.resize(deg);return res;}F& diff_inplace() {int n = (*this).size();for (int i = 1; i < n; ++i) (*this)[i - 1] = (*this)[i] * i;(*this)[n - 1] = 0;return *this;}F diff() const { F(*this).diff_inplace(); }F& integral_inplace() {int n = (*this).size(), mod = T::mod();std::vector<T> inv(n);{inv[1] = 1;for (int i = 2; i < n; ++i) inv[i] = T(mod) - inv[mod % i] * (mod / i);}for (int i = n - 2; i >= 0; --i) (*this)[i + 1] = (*this)[i] * inv[i + 1];(*this)[0] = 0;return *this;}F integral() const { return F(*this).integral_inplace(); }F& log_inplace() {int n = (*this).size();assert(n and (*this)[0] == 1);F f_inv = (*this).inv();(*this).diff_inplace();(*this) *= f_inv;(*this).integral_inplace();return *this;}F log() const { return F(*this).log_inplace(); }F& deriv_inplace() {int n = (*this).size();assert(n);for (int i = 2; i < n; ++i) (*this)[i] *= i;(*this).erase((*this).begin());(*this).push_back(0);return *this;}F deriv() const { return F(*this).deriv_inplace(); }F& exp_inplace() {int n = (*this).size();assert(n and (*this)[0] == 0);F g{1};(*this)[0] = 1;F h_drv((*this).deriv());for (int m = 1; m < n; m *= 2) {F f((*this).begin(), (*this).begin() + m);f.resize(2 * m), atcoder::internal::butterfly(f);auto mult_f = [&](F& p) {p.resize(2 * m);atcoder::internal::butterfly(p);for (int i = 0; i < 2 * m; ++i) p[i] *= f[i];atcoder::internal::butterfly_inv(p);p /= 2 * m;};if (m > 1) {F g_(g);g_.resize(2 * m), atcoder::internal::butterfly(g_);for (int i = 0; i < 2 * m; ++i) g_[i] *= g_[i] * f[i];atcoder::internal::butterfly_inv(g_);T iz = T(-2 * m).inv();g_ *= iz;g.insert(g.end(), g_.begin() + m / 2, g_.begin() + m);}F t((*this).begin(), (*this).begin() + m);t.deriv_inplace();{F r{h_drv.begin(), h_drv.begin() + m - 1};mult_f(r);for (int i = 0; i < m; ++i) t[i] -= r[i] + r[m + i];}t.insert(t.begin(), t.back());t.pop_back();t *= g;F v((*this).begin() + m, (*this).begin() + std::min(n, 2 * m));v.resize(m);t.insert(t.begin(), m - 1, 0);t.push_back(0);t.integral_inplace();for (int i = 0; i < m; ++i) v[i] -= t[m + i];mult_f(v);for (int i = 0; i < std::min(n - m, m); ++i) (*this)[m + i] = v[i];}return *this;}F exp() const { return F(*this).exp_inplace(); }F& pow_inplace(long long k) {int n = (*this).size(), l = 0;assert(k >= 0);if (!k) {for (int i = 0; i < n; ++i) (*this)[i] = !i;return *this;}while (l < n and (*this)[l] == 0) ++l;if (l > (n - 1) / k or l == n) return *this = F(n);T c = (*this)[l];(*this).erase((*this).begin(), (*this).begin() + l);(*this) /= c;(*this).log_inplace();(*this).resize(n - l * k);(*this) *= k;(*this).exp_inplace();(*this) *= c.pow(k);(*this).insert((*this).begin(), l * k, 0);return *this;}F pow(const long long k) const { return F(*this).pow_inplace(); }void spacemul(vector<pair<int, T>> g) {int n = (*this).size();auto [d, c] = g.front();if (d == 0)g.erase(g.begin());elsec = 0;for (int i = n - 1; i >= 0; i--) {(*this)[i] *= c;for (auto& [j, b] : g) {if (j > i) break;(*this)[i] += (*this)[i - j] * b;}}}void spacediv(vector<pair<int, T>> g) {int n = (*this).size();auto [d, c] = g.front();assert(d == 0 && c != T(0));T ic = c.inv();g.erase(g.begin());for (int i = 0; i < n; i++) {for (auto& [j, b] : g) {if (j > i) break;(*this)[i] -= (*this)[i - j] * b;}(*this)[i] *= ic;}}};using fps = FormalPowerSeries<atcoder::modint998244353, FAST>;mint g(ll a, ll b) {if (a == 1) {return mint(1);}if (b == 1) {return mint(1) / mint(2);}if (a == b) {return mint(1) / mint(mint(2).pow(a - 1) * k[a - 1]);}return mint(1) / mint(mint(2).pow(b)) * (mint(2) / mint(k[b - 1]) - mint(1) / mint(k[b]));}int main() {Scanner scanner;gbjsmzmfuuvdf();com();int n;n = in;assert(2 <= n && n <= 100000);mint h = mint(4).pow(n - 1);for (int i = 1; i <= n - 1; i++) {h *= i;}vector<mint> a(n), b(n);lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);for (int i = 0; i < n; i++) {seg.apply(i, g(n - i, 1));}for (int i = 2; i < n; i++) {seg.apply(i - 1, n - 1, g(n, i));}for (int i = 2; i <= n; i++) {seg.apply(n - 1, g(i, i));}for (int i = 0; i < n; i++) {int x;x = in;assert(0 <= x && x <= 2);a[i] = x;}mint ans = 0;for (int i = 0; i < n; i++) {ans += a[i] * seg.prod(i, i + 1).value;b[i] = seg.prod(i, i + 1).value;}for (int i = n - 1; i >= 0; i--) {a.push_back(a[i]);b.push_back(b[i]);}n *= 2;rever(b);vector<mint> c = convolution(a, b);for (int i = n; i < int(c.size()); i++) {c[i % n] += c[i];}c.resize(n);rever(c);fps f(n);f[0] = 1;cout << (c[0] * h / mint(2)).val() << "\n";int k = min(int(sqrt(n * log(n))), int(n));vector<vector<pair<int, mint>>> F(k + 1);vector<mint> p;F[0] = {{0, mint(1)}};for (int i = 1; i <= n / 2; i++) {ll v = i % k;if (v == i) {__gnu_pbds::gp_hash_table<int, mint> M;for (int j = 0; j < int(F[i - 1].size()); j++) {M[F[i - 1][j].fi] += (n / 2 - 3) * F[i - 1][j].se;M[(F[i - 1][j].fi - 1 + n) % n] += F[i - 1][j].se;M[(F[i - 1][j].fi + 1) % n] += F[i - 1][j].se;}for (auto e : M) {F[i].push_back({e.fi, e.se});}mint ans = 0;for (int j = 0; j < int(F[i].size()); j++) {ans += F[i][j].se * c[F[i][j].fi];}cout << (ans * h / mint(2)).val() << endl;} else {mint ans = 0;for (int j = 0; j < int(F[v].size()); j++) {ans += F[v][j].se * c[F[v][j].fi];}cout << (ans * h / mint(2)).val() << "\n";}if (i % k == k - 1) {if (int(p.size()) == 0) {__gnu_pbds::gp_hash_table<int, mint> M;for (int j = 0; j < int(F[k - 1].size()); j++) {M[F[k - 1][j].fi] += (n / 2 - 3) * F[k - 1][j].se;M[(F[k - 1][j].fi - 1 + n) % n] += F[k - 1][j].se;M[(F[k - 1][j].fi + 1) % n] += F[k - 1][j].se;}vector<pair<int, int>> S(int(M.size()));int now = 0;for (auto e : M) {if (e.fi >= n / 2) {S[now] = {e.fi - n, e.se.val()};} else {S[now] = {e.fi, e.se.val()};}now++;}sor(S);for (int j = 0; j < int(S.size()); j++) {p.push_back(S[j].se);}}auto d = convolution(c, p);for (int j = 0; j < int(c.size()); j++) {c[j] = 0;}for (int j = 0; j < int(d.size()); j++) {c[(j - k + n) % n] += d[j];}}}}