結果

問題 No.1189 Sum is XOR
ユーザー Chihaya_chanChihaya_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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 307 ms
168,548 KB
testcase_01 AC 303 ms
168,436 KB
testcase_02 AC 303 ms
168,644 KB
testcase_03 AC 61 ms
78,380 KB
testcase_04 AC 59 ms
75,472 KB
testcase_05 AC 69 ms
86,860 KB
testcase_06 AC 80 ms
99,692 KB
testcase_07 AC 64 ms
80,480 KB
testcase_08 AC 51 ms
67,228 KB
testcase_09 AC 51 ms
68,252 KB
testcase_10 AC 50 ms
66,348 KB
testcase_11 AC 269 ms
154,636 KB
testcase_12 AC 305 ms
169,204 KB
testcase_13 AC 298 ms
168,304 KB
testcase_14 AC 275 ms
152,752 KB
testcase_15 AC 266 ms
154,984 KB
testcase_16 AC 266 ms
155,404 KB
testcase_17 AC 264 ms
155,128 KB
testcase_18 AC 270 ms
153,820 KB
testcase_19 AC 281 ms
151,324 KB
testcase_20 AC 278 ms
151,260 KB
testcase_21 AC 264 ms
159,056 KB
testcase_22 AC 268 ms
159,344 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