結果

問題 No.3202 Periodic Alternating Subsequence
ユーザー fdironia
提出日時 2025-08-16 04:44:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 26 ms / 2,000 ms
コード長 2,103 bytes
コンパイル時間 857 ms
コンパイル使用メモリ 96,204 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-16 04:44:46
合計ジャッジ時間 2,665 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

using ll = long long;

constexpr int Z = 1e9+7;

struct Node {
    int cnt[2][2];
    int sum[2][2];
    int ssum[2][2];

    Node(int x = -1) {
        fill(cnt[0], cnt[2], 0);
        fill(sum[0], sum[2], 0);
        fill(ssum[0], ssum[2], 0);

        if (x == 0 || x == 1) {
            cnt[0][0] = cnt[1][0] = 1;
            cnt[x][1] = 1;
            sum[x][1] = 1;
            ssum[x][1] = 1;
        }
    }
};

void addm(int &a, int b) {
    a += b;
    if (a >= Z) {
        a -= Z;
    }
}

Node mul(Node a, Node b) {
    Node c;
    for (int i0 = 0; i0 < 2; i0++) {
        for (int j0 = 0; j0 < 2; j0++) {
            for (int i1 = 0; i1 < 2; i1++) {
                for (int j1 = 0; j1 < 2; j1++) {
                    if (i1 != (i0 + j0) % 2) {
                        continue;
                    }

                    addm(c.cnt[i0][(j0+j1)%2], 1ll * a.cnt[i0][j0] * b.cnt[i1][j1] % Z);
                    addm(c.sum[i0][(j0+j1)%2], (1ll * a.sum[i0][j0] * b.cnt[i1][j1] +
                                                1ll * b.sum[i1][j1] * a.cnt[i0][j0]) % Z);
                    addm(c.ssum[i0][(j0+j1)%2], (1ll * a.ssum[i0][j0] * b.cnt[i1][j1] +
                                                 1ll * b.ssum[i1][j1] * a.cnt[i0][j0] +
                                                 2ll * a.sum[i0][j0] * b.sum[i1][j1]) % Z);
                }
            }
        }
    }

    return c;
}

Node bexp(Node a, ll k) {
    if (k == 1) {
        return a;
    }

    if (k % 2 == 1) {
        return mul(bexp(a, k - 1), a);
    }

    Node t = bexp(a, k / 2);
    return mul(t, t);
}

int main() {
    string t;
    cin >> t;

    Node one = Node(t[0] - '0');
    for (int i = 1; i < (int)t.length(); i++) {
        one = mul(one, Node(t[i] - '0'));
    }

    ll k;
    cin >> k;
    Node fin = bexp(one, k);

    int ans = 0;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            addm(ans, fin.ssum[i][j]);
        }
    }

    cout << ans << endl;

    return 0;
}
0