結果

問題 No.3285 Chorus with Friends
コンテスト
ユーザー LyricalMaestro
提出日時 2026-03-22 23:18:05
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 3,454 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 313 ms
コンパイル使用メモリ 85,376 KB
実行使用メモリ 96,096 KB
最終ジャッジ日時 2026-03-22 23:18:22
合計ジャッジ時間 8,638 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

# 数論変換パートは
# https://qiita.com/AngrySadEight/items/0dfde26060daaf6a2fda
# と
# https://qiita.com/izu_nori/items/1c5cdef0500ffa0276f5
# を参考にしました

MOD = 998244353

def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(N):
        A.append(list(map(int, input().split())))


    # 取りうる値のチェック
    a_map = {}
    for i in range(N):
        a = A[i][0]
        if a not in a_map:
            a_map[a] = []
        a_map[a].append(i)
    
    answer = 0
    for a, index_list in a_map.items():
        if M <= 15:
            # 各種計算
            enables = [[False] * (2 ** M) for _ in range(len(index_list))]
            for index, i in enumerate(index_list):
                for bit in range(2 ** M):
                    steped = False
                    is_ok = True
                    for j in range(M):
                        if bit & (1 << j) > 0:
                            if not steped:
                                if j < M - 1 and A[i][j + 1] == a:
                                    continue
                                else:
                                    steped = True
                            else:
                                is_ok = False
                                break
                    if is_ok:
                        enables[index][bit] = True
            
            # dp
            dp = [0] * (2 ** M)
            for bit in range(2 ** M):
                if enables[0][bit]:
                    dp[bit] = 1
            for index in range(1, len(index_list)):
                en = enables[index]
                new_dp = [0] * (2 ** M)
                for base_bit in range(2 ** M):
                    bit = base_bit
                    while bit > 0:
                        b = base_bit - bit
                        if en[b]:
                            new_dp[base_bit] += dp[bit]
                            new_dp[base_bit] %= MOD
                        
                        bit = (bit - 1) & base_bit
                    if en[base_bit]:
                        new_dp[base_bit] += dp[0]
                        new_dp[base_bit] %= MOD
                dp = new_dp
            ans = dp[2 ** M - 1]
            answer += ans
            answer %= MOD
        else:
            dp = {0: 1}
            for m in range(M - 1):
                new_dp = {}
                for key_bit, value in dp.items():
                    for j in range(len(index_list)):
                        if key_bit & (1 << j) == 0:
                            if A[index_list[j]][m + 1] == a:
                                new_key_bit = key_bit
                            else:
                                new_key_bit = key_bit | (1 << j)
                            
                            if new_key_bit not in new_dp:
                                new_dp[new_key_bit] = 0
                            new_dp[new_key_bit] += value
                            new_dp[new_key_bit] %= MOD
                dp = new_dp
            
            ans = 0
            for key_bit, value in dp.items():
                for j in range(N):
                    if key_bit & (1 << j) == 0:
                        ans += value
                        ans %= MOD
            answer += ans
            answer %= MOD
    print(answer)




















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