#1104443 (C++17) No.3202 Periodic Alternating Subsequence

• 問題: No.3202 Periodic Alternating Subsequence
• ユーザー: theory_and_me
• 提出日時: 2025-07-12 16:49:09
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 173 ms / 2,000 ms
• コード長: 15,175 bytes
• コンパイル時間: 2,594 ms
• コンパイル使用メモリ: 211,888 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2025-07-12 16:49:16
• 合計ジャッジ時間: 6,482 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
sample	AC * 2
other	AC * 24

ソースコード

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using namespace atcoder;

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), lim##i = (b); i < lim##i; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define drep_(i, a_, b_, a, b, ...) for (int i = (a) - 1, lim##i = (b); i >= lim##i; --i)
#define drep(i, ...) drep_(i, __VA_ARGS__, __VA_ARGS__, __VA_ARGS__, 0)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#ifdef LOCAL
void debug_out() {
    cerr << endl;
}
template <class Head, class... Tail> void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}
#define debug(...) cerr << 'L' << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << 'L' << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
using ll = long long;
using ld = long double;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
template <class T> vector<T> make_vec(size_t n, T a) {
    return vector<T>(n, a);
}
template <class... Ts> auto make_vec(size_t n, Ts... ts) {
    return vector<decltype(make_vec(ts...))>(n, make_vec(ts...));
}
template <class T> inline void fin(const T x) {
    cout << x << '\n';
    exit(0);
}
template <class T> inline void deduplicate(vector<T> &a) {
    sort(all(a));
    a.erase(unique(all(a)), a.end());
}
template <class T> inline bool chmin(T &a, const T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, const T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline int sz(const T &x) {
    return x.size();
}
template <class T> inline int count_between(const vector<T> &a, T l, T r) {
    return lower_bound(all(a), r) - lower_bound(all(a), l);
}
template <class T1, class T2> istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}
template <class T1, class T2> ostream &operator<<(ostream &os, pair<T1, T2> &p) {
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}
template <class T, size_t n> istream &operator>>(istream &is, array<T, n> &v) {
    for (auto &e : v) is >> e;
    return is;
}
template <class T, size_t n> ostream &operator<<(ostream &os, array<T, n> &v) {
    for (auto &e : v) os << e << ' ';
    return os;
}
template <class T> istream &operator>>(istream &is, vector<T> &v) {
    for (auto &e : v) is >> e;
    return is;
}
template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
    for (auto &e : v) os << e << ' ';
    return os;
}
template <class T> istream &operator>>(istream &is, deque<T> &v) {
    for (auto &e : v) is >> e;
    return is;
}
template <class T> ostream &operator<<(ostream &os, deque<T> &v) {
    for (auto &e : v) os << e << ' ';
    return os;
}
inline ll floor_div(ll x, ll y) {
    if (y < 0) x = -x, y = -y;
    return x >= 0 ? x / y : (x - y + 1) / y;
}
inline ll ceil_div(ll x, ll y) {
    if (y < 0) x = -x, y = -y;
    return x >= 0 ? (x + y - 1) / y : x / y;
}
inline int floor_log2(const ll x) {
    assert(x > 0);
    return 63 - __builtin_clzll(x);
}
inline int ceil_log2(const ll x) {
    assert(x > 0);
    return (x == 1) ? 0 : 64 - __builtin_clzll(x - 1);
}
inline int popcount(const ll x) {
    return __builtin_popcountll(x);
}
struct fast_ios {
    fast_ios() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    };
} fast_ios;

// 時間計測
auto system_now = std::chrono::system_clock::now();
int check_time() {
    auto now = std::chrono::system_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(now - system_now).count();
}

// 乱数
struct Xorshift {
    uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;

    uint32_t rand_int() {
        uint32_t t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }

    // 0以上mod未満の整数を乱択
    uint32_t rand_int(uint32_t mod) {
        return rand_int() % mod;
    }

    // l以上r未満の整数を乱択
    uint32_t rand_int(uint32_t l, uint32_t r) {
        assert(l < r);
        return l + rand_int(r - l);
    }

    // 0以上1以下の実数を乱沢
    double rand_double() {
        return (double)rand_int() / UINT32_MAX;
    }
};
Xorshift xor_shift;

// constexpr int INF = numeric_limits<int>::max() >> 2;
// constexpr ll INFll = numeric_limits<ll>::max() >> 2;
// constexpr ld EPS = 1e-10;
// const ld PI = acos(-1.0);
// using mint = modint998244353;
using mint = modint1000000007;
// using mint = modint;
// using Vm = V<mint>; using VVm = VV<mint>;

namespace matrix_ {
struct has_id_method_impl {
    template <class T_> static auto check(T_ *) -> decltype(T_::id(), std::true_type());
    template <class T_> static auto check(...) -> std::false_type;
};
template <class T_> struct has_id : decltype(has_id_method_impl::check<T_>(nullptr)) {};
}  // namespace matrix_

template <typename T> struct matrix {
    int H, W;
    std::vector<T> elem;
    typename std::vector<T>::iterator operator[](int i) {
        return elem.begin() + i * W;
    }
    inline T &at(int i, int j) {
        return elem[i * W + j];
    }
    inline T get(int i, int j) const {
        return elem[i * W + j];
    }
    int height() const {
        return H;
    }
    int width() const {
        return W;
    }
    std::vector<std::vector<T>> vecvec() const {
        std::vector<std::vector<T>> ret(H);
        for (int i = 0; i < H; i++) {
            std::copy(elem.begin() + i * W, elem.begin() + (i + 1) * W, std::back_inserter(ret[i]));
        }
        return ret;
    }
    operator std::vector<std::vector<T>>() const {
        return vecvec();
    }
    matrix() = default;
    matrix(int H, int W)
        : H(H), W(W), elem(H * W) {
    }
    matrix(const std::vector<std::vector<T>> &d)
        : H(d.size()), W(d.size() ? d[0].size() : 0) {
        for (auto &raw : d) std::copy(raw.begin(), raw.end(), std::back_inserter(elem));
    }

    template <typename T2, typename std::enable_if<matrix_::has_id<T2>::value>::type * = nullptr>
    static T2 _T_id() {
        return T2::id();
    }
    template <typename T2, typename std::enable_if<!matrix_::has_id<T2>::value>::type * = nullptr>
    static T2 _T_id() {
        return T2(1);
    }

    static matrix Identity(int N) {
        matrix ret(N, N);
        for (int i = 0; i < N; i++) ret.at(i, i) = _T_id<T>();
        return ret;
    }

    matrix operator-() const {
        matrix ret(H, W);
        for (int i = 0; i < H * W; i++) ret.elem[i] = -elem[i];
        return ret;
    }
    matrix operator*(const T &v) const {
        matrix ret = *this;
        for (auto &x : ret.elem) x *= v;
        return ret;
    }
    matrix operator/(const T &v) const {
        matrix ret = *this;
        const T vinv = _T_id<T>() / v;
        for (auto &x : ret.elem) x *= vinv;
        return ret;
    }
    matrix operator+(const matrix &r) const {
        matrix ret = *this;
        for (int i = 0; i < H * W; i++) ret.elem[i] += r.elem[i];
        return ret;
    }
    matrix operator-(const matrix &r) const {
        matrix ret = *this;
        for (int i = 0; i < H * W; i++) ret.elem[i] -= r.elem[i];
        return ret;
    }
    matrix operator*(const matrix &r) const {
        matrix ret(H, r.W);
        for (int i = 0; i < H; i++) {
            for (int k = 0; k < W; k++) {
                for (int j = 0; j < r.W; j++) ret.at(i, j) += this->get(i, k) * r.get(k, j);
            }
        }
        return ret;
    }
    matrix &operator*=(const T &v) {
        return *this = *this * v;
    }
    matrix &operator/=(const T &v) {
        return *this = *this / v;
    }
    matrix &operator+=(const matrix &r) {
        return *this = *this + r;
    }
    matrix &operator-=(const matrix &r) {
        return *this = *this - r;
    }
    matrix &operator*=(const matrix &r) {
        return *this = *this * r;
    }
    bool operator==(const matrix &r) const {
        return H == r.H and W == r.W and elem == r.elem;
    }
    bool operator!=(const matrix &r) const {
        return H != r.H or W != r.W or elem != r.elem;
    }
    bool operator<(const matrix &r) const {
        return elem < r.elem;
    }
    matrix pow(int64_t n) const {
        matrix ret = Identity(H);
        bool ret_is_id = true;
        if (n == 0) return ret;
        for (int i = 63 - __builtin_clzll(n); i >= 0; i--) {
            if (!ret_is_id) ret *= ret;
            if ((n >> i) & 1) ret *= (*this), ret_is_id = false;
        }
        return ret;
    }
    std::vector<T> pow_vec(int64_t n, std::vector<T> vec) const {
        matrix x = *this;
        while (n) {
            if (n & 1) vec = x * vec;
            x *= x;
            n >>= 1;
        }
        return vec;
    };
    matrix transpose() const {
        matrix ret(W, H);
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) ret.at(j, i) = this->get(i, j);
        }
        return ret;
    }
    // Gauss-Jordan elimination
    // - Require inverse for every non-zero element
    // - Complexity: O(H^2 W)
    template <typename T2, typename std::enable_if<std::is_floating_point<T2>::value>::type * = nullptr>
    static int choose_pivot(const matrix<T2> &mtr, int h, int c) noexcept {
        int piv = -1;
        for (int j = h; j < mtr.H; j++) {
            if (mtr.get(j, c) and (piv < 0 or std::abs(mtr.get(j, c)) > std::abs(mtr.get(piv, c))))
                piv = j;
        }
        return piv;
    }
    template <typename T2, typename std::enable_if<!std::is_floating_point<T2>::value>::type * = nullptr>
    static int choose_pivot(const matrix<T2> &mtr, int h, int c) noexcept {
        for (int j = h; j < mtr.H; j++) {
            if (mtr.get(j, c) != T2()) return j;
        }
        return -1;
    }
    matrix gauss_jordan() const {
        int c = 0;
        matrix mtr(*this);
        std::vector<int> ws;
        ws.reserve(W);
        for (int h = 0; h < H; h++) {
            if (c == W) break;
            int piv = choose_pivot(mtr, h, c);
            if (piv == -1) {
                c++;
                h--;
                continue;
            }
            if (h != piv) {
                for (int w = 0; w < W; w++) {
                    std::swap(mtr[piv][w], mtr[h][w]);
                    mtr.at(piv, w) *= -_T_id<T>();  // To preserve sign of determinant
                }
            }
            ws.clear();
            for (int w = c; w < W; w++) {
                if (mtr.at(h, w) != T()) ws.emplace_back(w);
            }
            const T hcinv = _T_id<T>() / mtr.at(h, c);
            for (int hh = 0; hh < H; hh++)
                if (hh != h) {
                    const T coeff = mtr.at(hh, c) * hcinv;
                    for (auto w : ws) mtr.at(hh, w) -= mtr.at(h, w) * coeff;
                    mtr.at(hh, c) = T();
                }
            c++;
        }
        return mtr;
    }
    int rank_of_gauss_jordan() const {
        for (int i = H * W - 1; i >= 0; i--) {
            if (elem[i] != 0) return i / W + 1;
        }
        return 0;
    }
    int rank() const {
        return gauss_jordan().rank_of_gauss_jordan();
    }

    T determinant_of_upper_triangle() const {
        T ret = _T_id<T>();
        for (int i = 0; i < H; i++) ret *= get(i, i);
        return ret;
    }
    int inverse() {
        assert(H == W);
        std::vector<std::vector<T>> ret = Identity(H), tmp = *this;
        int rank = 0;
        for (int i = 0; i < H; i++) {
            int ti = i;
            while (ti < H and tmp[ti][i] == 0) ti++;
            if (ti == H) {
                continue;
            } else {
                rank++;
            }
            ret[i].swap(ret[ti]), tmp[i].swap(tmp[ti]);
            T inv = _T_id<T>() / tmp[i][i];
            for (int j = 0; j < W; j++) ret[i][j] *= inv;
            for (int j = i + 1; j < W; j++) tmp[i][j] *= inv;
            for (int h = 0; h < H; h++) {
                if (i == h) continue;
                const T c = -tmp[h][i];
                for (int j = 0; j < W; j++) ret[h][j] += ret[i][j] * c;
                for (int j = i + 1; j < W; j++) tmp[h][j] += tmp[i][j] * c;
            }
        }
        *this = ret;
        return rank;
    }
    friend std::vector<T> operator*(const matrix &m, const std::vector<T> &v) {
        assert(m.W == int(v.size()));
        std::vector<T> ret(m.H);
        for (int i = 0; i < m.H; i++) {
            for (int j = 0; j < m.W; j++) ret[i] += m.get(i, j) * v[j];
        }
        return ret;
    }
    friend std::vector<T> operator*(const std::vector<T> &v, const matrix &m) {
        assert(int(v.size()) == m.H);
        std::vector<T> ret(m.W);
        for (int i = 0; i < m.H; i++) {
            for (int j = 0; j < m.W; j++) ret[j] += v[i] * m.get(i, j);
        }
        return ret;
    }
    std::vector<T> prod(const std::vector<T> &v) const {
        return (*this) * v;
    }
    std::vector<T> prod_left(const std::vector<T> &v) const {
        return v * (*this);
    }
    template <class OStream> friend OStream &operator<<(OStream &os, const matrix &x) {
        os << "[(" << x.H << " * " << x.W << " matrix)";
        os << "\n[column sums: ";
        for (int j = 0; j < x.W; j++) {
            T s = 0;
            for (int i = 0; i < x.H; i++) s += x.get(i, j);
            os << s << ",";
        }
        os << "]";
        for (int i = 0; i < x.H; i++) {
            os << "\n[";
            for (int j = 0; j < x.W; j++) os << x.get(i, j) << ",";
            os << "]";
        }
        os << "]\n";
        return os;
    }
    template <class IStream> friend IStream &operator>>(IStream &is, matrix &x) {
        for (auto &v : x.elem) is >> v;
        return is;
    }
};

vector<vector<mint>> T0 = {
    {1, 0, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 0, 0, 0},
    {0, 0, 1, 0, 0, 0, 0},
    {1, 0, 1, 1, 1, 0, 0},
    {0, 0, 0, 0, 1, 0, 0},
    {1, 0, 1, 0, 2, 1, 1},
    {0, 0, 0, 0, 0, 0, 1}};

vector<vector<mint>> T1 = {
    {1, 0, 0, 0, 0, 0, 0},
    {0, 1, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 0, 0, 0},
    {0, 0, 0, 1, 0, 0, 0},
    {1, 1, 0, 1, 1, 0, 0},
    {0, 0, 0, 0, 0, 1, 0},
    {1, 1, 0, 2, 0, 1, 1}};

vector<vector<mint>> E = {
    {1, 0, 0, 0, 0, 0, 0},
    {0, 1, 0, 0, 0, 0, 0},
    {0, 0, 1, 0, 0, 0, 0},
    {0, 0, 0, 1, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 1, 0},
    {0, 0, 0, 0, 0, 0, 1}};

int main() {
    string T;
    cin >> T;
    ll K;
    cin >> K;

    matrix<mint> T0_mat(T0), T1_mat(T1), E_mat(E);

    matrix<mint> TT = E_mat;
    for (char c : T) {
        if (c == '0') {
            TT = T0_mat * TT;
        } else {
            TT = T1_mat * TT;
        }
    }
    TT = TT.pow(K);
    matrix<mint> b(7, 1);
    b.at(0, 0) = 1;  // 初期状態は 1

    b = TT * b;
    cout << (b.at(5, 0) + b.at(6, 0)).val() << '\n';  // 5番目と6番目の状態の和が答え

    return 0;
}