結果

問題 No.1840 Random Painting
ユーザー hitonanodehitonanode
提出日時 2021-12-19 18:38:57
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,531 ms / 2,000 ms
コード長 7,668 bytes
コンパイル時間 7,900 ms
コンパイル使用メモリ 259,696 KB
実行使用メモリ 50,560 KB
最終ジャッジ日時 2024-06-27 15:59:12
合計ジャッジ時間 25,871 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 10 ms
7,144 KB
testcase_06 AC 64 ms
32,244 KB
testcase_07 AC 8 ms
5,376 KB
testcase_08 AC 8 ms
5,376 KB
testcase_09 AC 66 ms
8,208 KB
testcase_10 AC 667 ms
39,628 KB
testcase_11 AC 1,142 ms
46,460 KB
testcase_12 AC 626 ms
40,312 KB
testcase_13 AC 134 ms
50,560 KB
testcase_14 AC 1,477 ms
47,356 KB
testcase_15 AC 1,044 ms
46,076 KB
testcase_16 AC 1,212 ms
46,588 KB
testcase_17 AC 419 ms
39,420 KB
testcase_18 AC 1,521 ms
47,488 KB
testcase_19 AC 1,523 ms
47,484 KB
testcase_20 AC 1,524 ms
47,484 KB
testcase_21 AC 1,521 ms
47,480 KB
testcase_22 AC 1,513 ms
47,480 KB
testcase_23 AC 1,531 ms
47,488 KB
testcase_24 AC 31 ms
10,392 KB
testcase_25 AC 86 ms
38,736 KB
testcase_26 AC 89 ms
38,644 KB
testcase_27 AC 31 ms
10,268 KB
testcase_28 AC 89 ms
38,644 KB
testcase_29 AC 89 ms
38,776 KB
testcase_30 AC 63 ms
32,372 KB
testcase_31 AC 64 ms
32,376 KB
testcase_32 AC 64 ms
32,368 KB
testcase_33 AC 64 ms
32,244 KB
testcase_34 AC 64 ms
32,240 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Validator
#include <iostream>
#include <set>
#include <string>
#include <vector>
#include "testlib.h"
using namespace std;

template <int md> struct ModInt {
#if __cplusplus >= 201402L
#define MDCONST constexpr
#else
#define MDCONST
#endif
    using lint = long long;
    MDCONST static int mod() { return md; }
    static int get_primitive_root() {
        static int primitive_root = 0;
        if (!primitive_root) {
            primitive_root = [&]() {
                std::set<int> fac;
                int v = md - 1;
                for (lint i = 2; i * i <= v; i++)
                    while (v % i == 0) fac.insert(i), v /= i;
                if (v > 1) fac.insert(v);
                for (int g = 1; g < md; g++) {
                    bool ok = true;
                    for (auto i : fac)
                        if (ModInt(g).pow((md - 1) / i) == 1) {
                            ok = false;
                            break;
                        }
                    if (ok) return g;
                }
                return -1;
            }();
        }
        return primitive_root;
    }
    int val;
    MDCONST ModInt() : val(0) {}
    MDCONST ModInt &_setval(lint v) { return val = (v >= md ? v - md : v), *this; }
    MDCONST ModInt(lint v) { _setval(v % md + md); }
    MDCONST explicit operator bool() const { return val != 0; }
    MDCONST ModInt operator+(const ModInt &x) const { return ModInt()._setval((lint)val + x.val); }
    MDCONST ModInt operator-(const ModInt &x) const { return ModInt()._setval((lint)val - x.val + md); }
    MDCONST ModInt operator*(const ModInt &x) const { return ModInt()._setval((lint)val * x.val % md); }
    MDCONST ModInt operator/(const ModInt &x) const { return ModInt()._setval((lint)val * x.inv() % md); }
    MDCONST ModInt operator-() const { return ModInt()._setval(md - val); }
    MDCONST ModInt &operator+=(const ModInt &x) { return *this = *this + x; }
    MDCONST ModInt &operator-=(const ModInt &x) { return *this = *this - x; }
    MDCONST ModInt &operator*=(const ModInt &x) { return *this = *this * x; }
    MDCONST ModInt &operator/=(const ModInt &x) { return *this = *this / x; }
    friend MDCONST ModInt operator+(lint a, const ModInt &x) { return ModInt()._setval(a % md + x.val); }
    friend MDCONST ModInt operator-(lint a, const ModInt &x) { return ModInt()._setval(a % md - x.val + md); }
    friend MDCONST ModInt operator*(lint a, const ModInt &x) { return ModInt()._setval(a % md * x.val % md); }
    friend MDCONST ModInt operator/(lint a, const ModInt &x) {
        return ModInt()._setval(a % md * x.inv() % md);
    }
    MDCONST bool operator==(const ModInt &x) const { return val == x.val; }
    MDCONST bool operator!=(const ModInt &x) const { return val != x.val; }
    MDCONST bool operator<(const ModInt &x) const { return val < x.val; } // To use std::map<ModInt, T>
    friend std::istream &operator>>(std::istream &is, ModInt &x) {
        lint t;
        return is >> t, x = ModInt(t), is;
    }
    MDCONST friend std::ostream &operator<<(std::ostream &os, const ModInt &x) { return os << x.val; }
    MDCONST ModInt pow(lint n) const {
        ModInt ans = 1, tmp = *this;
        while (n) {
            if (n & 1) ans *= tmp;
            tmp *= tmp, n >>= 1;
        }
        return ans;
    }

    static std::vector<ModInt> facs, facinvs, invs;
    MDCONST static void _precalculation(int N) {
        int l0 = facs.size();
        if (N > md) N = md;
        if (N <= l0) return;
        facs.resize(N), facinvs.resize(N), invs.resize(N);
        for (int i = l0; i < N; i++) facs[i] = facs[i - 1] * i;
        facinvs[N - 1] = facs.back().pow(md - 2);
        for (int i = N - 2; i >= l0; i--) facinvs[i] = facinvs[i + 1] * (i + 1);
        for (int i = N - 1; i >= l0; i--) invs[i] = facinvs[i] * facs[i - 1];
    }
    MDCONST lint inv() const {
        if (this->val < std::min(md >> 1, 1 << 21)) {
            while (this->val >= int(facs.size())) _precalculation(facs.size() * 2);
            return invs[this->val].val;
        } else {
            return this->pow(md - 2).val;
        }
    }
    MDCONST ModInt fac() const {
        while (this->val >= int(facs.size())) _precalculation(facs.size() * 2);
        return facs[this->val];
    }
    MDCONST ModInt facinv() const {
        while (this->val >= int(facs.size())) _precalculation(facs.size() * 2);
        return facinvs[this->val];
    }
    MDCONST ModInt doublefac() const {
        lint k = (this->val + 1) / 2;
        return (this->val & 1) ? ModInt(k * 2).fac() / (ModInt(2).pow(k) * ModInt(k).fac())
                               : ModInt(k).fac() * ModInt(2).pow(k);
    }
    MDCONST ModInt nCr(const ModInt &r) const {
        return (this->val < r.val) ? 0 : this->fac() * (*this - r).facinv() * r.facinv();
    }
    MDCONST ModInt nPr(const ModInt &r) const {
        return (this->val < r.val) ? 0 : this->fac() * (*this - r).facinv();
    }

    ModInt sqrt() const {
        if (val == 0) return 0;
        if (md == 2) return val;
        if (pow((md - 1) / 2) != 1) return 0;
        ModInt b = 1;
        while (b.pow((md - 1) / 2) == 1) b += 1;
        int e = 0, m = md - 1;
        while (m % 2 == 0) m >>= 1, e++;
        ModInt x = pow((m - 1) / 2), y = (*this) * x * x;
        x *= (*this);
        ModInt z = b.pow(m);
        while (y != 1) {
            int j = 0;
            ModInt t = y;
            while (t != 1) j++, t *= t;
            z = z.pow(1LL << (e - j - 1));
            x *= z, z *= z, y *= z;
            e = j;
        }
        return ModInt(std::min(x.val, md - x.val));
    }
};
template <int md> std::vector<ModInt<md>> ModInt<md>::facs = {1};
template <int md> std::vector<ModInt<md>> ModInt<md>::facinvs = {1};
template <int md> std::vector<ModInt<md>> ModInt<md>::invs = {0};
using mint1 = ModInt<998244353>;
using mint2 = ModInt<1000000007>;

#include <atcoder/math>

template <class Mint> Mint A107984(Mint n, Mint k) { return (k + 1) * (n + 2) * (2 * n - k + 3) * (n - k + 1) / 6; }

// 右に r ステップ進むより左に l ステップ進む方が先の確率 * （そのようなときにそれを達成するまでの時間の条件付き期待値）
template <class Mint> Mint solve(int l, int r) {
    int N = l + r;
    return A107984<Mint>(N - 2, l - 1) * 2 / (Mint(N) * N);
}

template <class Mint> Mint sol(const string &S) {
    const int N = S.size();
    vector<int> zeropos;
    for (int i = 0; i < N; i++) {
        if (S[i] == '1') continue;
        zeropos.push_back(i);
    }
    Mint ret = solve<Mint>(N - zeropos[0], zeropos[0]) + solve<Mint>(zeropos.back(), N - zeropos.back());

    for (int i = 1; i < int(zeropos.size()); ++i) {
        int a = zeropos[i - 1], b = zeropos[i];
        for (int t = 0; t < 2; ++t) {
            Mint e1 = solve<Mint>(a, N - b);
            Mint e2 = solve<Mint>(N - (b - a), b - a);
            ret += e1 * (b - a) / N + e2 * (N - b) / (N - b + a);
            swap(a, b);
            a = N - a;
            b = N - b;
        }
    }
    return ret;
}

int main(int argc, char **argv) {
    registerValidation(argc, argv);

    int N = inf.readInt(2, 1000000);
    inf.readEoln();
    string S = inf.readString();
    inf.readEof();

    for (auto c : S) assert(c == '0' or c == '1');
    assert(int(S.size()) == N);

    auto v1 = sol<mint1>(S).val;
    auto v2 = sol<mint2>(S).val;
    cout << atcoder::crt({v1, v2}, {mint1::mod(), mint2::mod()}).first << '\n';
}
0