結果

問題 No.1189 Sum is XOR
ユーザー Chihaya_chanChihaya_chan
提出日時 2020-09-02 23:11:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 310 ms / 2,000 ms
コード長 985 bytes
コンパイル時間 461 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 168,832 KB
最終ジャッジ日時 2024-05-01 18:45:08
合計ジャッジ時間 6,934 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 264 ms
168,816 KB
testcase_01 AC 270 ms
168,692 KB
testcase_02 AC 271 ms
168,832 KB
testcase_03 AC 53 ms
78,016 KB
testcase_04 AC 48 ms
75,156 KB
testcase_05 AC 60 ms
86,140 KB
testcase_06 AC 72 ms
99,512 KB
testcase_07 AC 55 ms
80,056 KB
testcase_08 AC 44 ms
66,572 KB
testcase_09 AC 47 ms
67,588 KB
testcase_10 AC 43 ms
65,480 KB
testcase_11 AC 234 ms
154,940 KB
testcase_12 AC 310 ms
168,692 KB
testcase_13 AC 274 ms
168,452 KB
testcase_14 AC 250 ms
152,388 KB
testcase_15 AC 241 ms
155,144 KB
testcase_16 AC 231 ms
155,432 KB
testcase_17 AC 231 ms
155,296 KB
testcase_18 AC 235 ms
153,704 KB
testcase_19 AC 243 ms
151,452 KB
testcase_20 AC 247 ms
151,104 KB
testcase_21 AC 242 ms
159,080 KB
testcase_22 AC 235 ms
159,012 KB
権限があれば一括ダウンロードができます

ソースコード

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