#1190414 (Python3) No.3716 Keep it Integer

• 問題: No.3716 Keep it Integer
• ユーザー: seroze
• 提出日時: 2026-09-24 03:00:43
• 言語: Python3 (3.14.7 + numpy 2.5.2 + scipy 1.18.0 + ACL)
• 結果: AC
• 実行時間: 1,675 ms / 2,000 ms
• コード長: 4,069 bytes
• コンパイル時間: 56 ms
• コンパイル使用メモリ: 15,232 KB
• 実行使用メモリ: 53,264 KB
• 最終ジャッジ日時: 2026-09-24 03:01:17
• 合計ジャッジ時間: 30,414 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_0

ファイルパターン	結果
sample	AC * 3
other	AC * 50

ソースコード

MOD = 998244353
MAXV = 10**18


def solve():
    import sys

    input = sys.stdin.readline

    N, X = map(int, input().split())
    A = list(map(int, input().split()))
    A = [0] + A

    # f[i] = number of valid sequences whose i-th operation is type 1
    # g[i] = number of valid sequences whose i-th operation is type 2
    #
    # f[0] = 1 represents the empty prefix.
    f = [0] * (N + 1)
    g = [0] * (N + 1)

    f[0] = 1

    # prefix_f[i] = f[0] + ... + f[i]
    prefix_f = [0] * (N + 1)
    prefix_f[0] = 1

    # Positions whose A[pos] != 1.
    non_one = []

    # Product A[1] * ... * A[i], capped above 1e18.
    prefix_product = 1

    for i in range(1, N + 1):

        # A type-1 operation can always be performed.
        f[i] = (f[i - 1] + g[i - 1]) % MOD

        # ------------------------------------------------------------
        # Compute g[i]
        # ------------------------------------------------------------

        ways = 0

        # ------------------------------------------------------------
        # Case 1:
        # The entire 2-block consists only of 1's.
        #
        # Suppose p is the last non-1 position before i.
        # Then the block can start anywhere in [p+1, i].
        #
        # Product of the block = 1, so every such start is valid.
        # ------------------------------------------------------------

        if A[i] == 1:
            if non_one:
                p = non_one[-1]

                # starts j = p+1 ... i
                # corresponding previous type-1 positions are
                # p ... i-1
                ways += prefix_f[i - 1] - prefix_f[p - 1]
            else:
                # Everything A[1..i] is 1.
                # starts j = 1 ... i
                # corresponding f[j-1] = f[0] ... f[i-1]
                ways += prefix_f[i - 1]

            ways %= MOD

        # ------------------------------------------------------------
        # Case 2:
        # The 2-block contains at least one non-1.
        #
        # Let q be the position immediately before the block.
        # q must have been a type-1 operation, contributing f[q].
        #
        # We need:
        #
        #     A[q+1] * ... * A[i] | A[q]
        #
        # Iterate over q's that have A[q] != 1.
        # ------------------------------------------------------------

        if non_one:
            # Initially product = A[i].
            #
            # For the current q:
            #     product = A[q+1] * ... * A[i]
            #
            # Then after processing q, multiply by A[q] before
            # moving to the previous non-1 position.
            product = A[i]

            for q in reversed(non_one):

                if product > MAXV:
                    break

                if product > 1 and A[q] % product == 0:
                    ways += f[q]

                    if ways >= MOD:
                        ways -= MOD

                # For the next q:
                # product becomes A[q] * ... * A[i]
                product *= A[q]

                if product > MAXV:
                    break

        # ------------------------------------------------------------
        # Case 3:
        # The 2-block starts at position 1.
        #
        # Then the value before the block is X rather than A[q].
        #
        # Need:
        #
        #     A[1] * ... * A[i] | X
        #
        # ------------------------------------------------------------

        prefix_product *= A[i]

        if prefix_product > MAXV:
            prefix_product = MAXV + 1

        if prefix_product > 1 and prefix_product <= X:
            if X % prefix_product == 0:
                ways += 1

                if ways >= MOD:
                    ways -= MOD

        g[i] = ways % MOD

        # Update prefix sum of f.
        prefix_f[i] = (prefix_f[i - 1] + f[i]) % MOD

        # We only need non-1 positions for the backward jumps.
        if A[i] != 1:
            non_one.append(i)

    print((f[N] + g[N]) % MOD)


if __name__ == "__main__":
    solve()