#668578 (C++17) No.1574 Swap and Repaint

提出ソース
結果

問題	No.1574 Swap and Repaint
ユーザー	KoD
提出日時	2021-06-20 17:26:14
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	5,544 ms / 10,000 ms
コード長	17,334 bytes
コンパイル時間	8,298 ms
コンパイル使用メモリ	338,084 KB
実行使用メモリ	43,416 KB
最終ジャッジ日時	2024-10-03 12:24:27
合計ジャッジ時間	35,133 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 5,248 KB
testcase_01	AC	4 ms 5,248 KB
testcase_02	AC	4 ms 5,248 KB
testcase_03	AC	4 ms 5,248 KB
testcase_04	AC	4 ms 5,248 KB
testcase_05	AC	4 ms 5,248 KB
testcase_06	AC	3 ms 5,376 KB
testcase_07	AC	4 ms 5,248 KB
testcase_08	AC	4 ms 5,248 KB
testcase_09	AC	8 ms 5,632 KB
testcase_10	AC	5 ms 5,376 KB
testcase_11	AC	5 ms 5,376 KB
testcase_12	AC	9 ms 5,504 KB
testcase_13	AC	7 ms 5,504 KB
testcase_14	AC	7 ms 5,504 KB
testcase_15	AC	9 ms 5,632 KB
testcase_16	AC	4 ms 5,376 KB
testcase_17	AC	5 ms 5,504 KB
testcase_18	AC	820 ms 15,808 KB
testcase_19	AC	5,544 ms 41,800 KB
testcase_20	AC	507 ms 16,768 KB
testcase_21	AC	357 ms 14,808 KB
testcase_22	AC	446 ms 13,796 KB
testcase_23	AC	71 ms 7,676 KB
testcase_24	AC	1,488 ms 36,156 KB
testcase_25	AC	1,401 ms 22,664 KB
testcase_26	AC	24 ms 6,144 KB
testcase_27	AC	335 ms 12,216 KB
testcase_28	AC	1,821 ms 43,288 KB
testcase_29	AC	1,915 ms 43,292 KB
testcase_30	AC	1,856 ms 43,284 KB
testcase_31	AC	1,865 ms 43,288 KB
testcase_32	AC	1,872 ms 43,292 KB
testcase_33	AC	1,858 ms 43,288 KB
testcase_34	AC	1,805 ms 43,292 KB
testcase_35	AC	1,799 ms 43,416 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/extc++.h>
#include <unistd.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using 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);
    else
        return 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());
        else
            c = 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];
            }
        }
    }
}
yukicoder

結果

テストケース

ソースコード
