結果

問題 No.1189 Sum is XOR
ユーザー Chihaya_chan
提出日時 2020-09-02 23:11:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 307 ms / 2,000 ms
コード長 985 bytes
コンパイル時間 444 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 169,204 KB
最終ジャッジ日時 2024-11-22 00:39:52
合計ジャッジ時間 7,520 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    N, K = map(int, input().split())
    mod = 998244353
    A = list(map(int, input().split()))
    if K > 10:
        print(0)
        return
    else:
        cnt = [0 for i in range(1 << 10)]
        for x in A:
            cnt[x] += 1
        dp = [[[0]*(1 << 10) for j in range(11)]for i in range(1 << 10)]
        dp[0][0][0] = 1
        for number in range(1, 1 << 10):
            for used in range(11):
                for xor_value in range(1 << 10):
                    if (xor_value-number) & number == 0 and used > 0:
                        dp[number][used][xor_value] = (
                            dp[number - 1][used][xor_value] + dp[number - 1][used - 1][xor_value ^ number]*cnt[number]) % mod
                    else:
                        dp[number][used][xor_value] = dp[number - 1][used][xor_value]

        ans = sum(dp[(1 << 10) - 1][K][x] for x in range(1 << 10)) % mod
        print(ans)
        return


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