結果

問題 No.2561 みんな大好きmod 998
コンテスト
ユーザー LyricalMaestro
提出日時 2025-06-12 02:03:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 88 ms / 4,000 ms
コード長 1,254 bytes
コンパイル時間 766 ms
コンパイル使用メモリ 82,416 KB
実行使用メモリ 76,512 KB
最終ジャッジ日時 2025-06-12 02:03:58
合計ジャッジ時間 5,403 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2561

MOD1 = 998
MOD2 = 998244353

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    if N == 1:
        a = A[0]
        if a % MOD2 <= a % MOD1:
            print(1)
        else:
            print(0)
        return
    
    # 半分全列挙
    N1 = N // 2
    N2 = N - N1

    array_map = [[] for _ in range(K + 1)]
    for bit in range(2 ** N1):
        c = 0
        s = 0
        for i in range(N1):
            if bit & (1 << i) > 0:
                c += 1
                s += A[i]

        if c <= K:
            array_map[c].append(s)
    array_map2 = [[] for _ in range(K + 1)]
    for bit in range(2 ** N2):
        c = 0
        s = 0
        for i in range(N2):
            if bit & (1 << i) > 0:
                c += 1
                s += A[i + N1]

        if c <= K:
            array_map2[c].append(s)

    answer = 0    
    for c1 in range(K + 1):
        c2 = K - c1
        for a in array_map[c1]:
            for b in array_map2[c2]:
                s = a + b
                if s % MOD2 <= s % MOD1:
                    answer += 1
                    answer %= MOD1
    print(answer)

    
        











if __name__ == "__main__":
    main()
0