結果
問題 | No.641 Team Contest Estimation |
ユーザー | fine |
提出日時 | 2018-01-27 23:38:45 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,352 ms / 2,000 ms |
コード長 | 803 bytes |
コンパイル時間 | 117 ms |
コンパイル使用メモリ | 10,992 KB |
実行使用メモリ | 18,716 KB |
最終ジャッジ日時 | 2023-08-28 10:04:58 |
合計ジャッジ時間 | 6,530 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 19 ms
7,796 KB |
testcase_01 | AC | 18 ms
7,848 KB |
testcase_02 | AC | 16 ms
7,796 KB |
testcase_03 | AC | 16 ms
7,836 KB |
testcase_04 | AC | 16 ms
7,776 KB |
testcase_05 | AC | 1,343 ms
18,716 KB |
testcase_06 | AC | 1,342 ms
18,620 KB |
testcase_07 | AC | 1,347 ms
18,644 KB |
testcase_08 | AC | 1,352 ms
18,692 KB |
testcase_09 | AC | 15 ms
7,848 KB |
testcase_10 | AC | 16 ms
7,892 KB |
ソースコード
MOD = 1000000009 n, k = map(int, input().strip().split()) a = map(int, input().strip().split()) if k == 0: print(0) print(0) else: ans1 = n * (pow(2, k, MOD) + MOD - 1) * pow(2, k - 1, MOD) % MOD print(ans1) cnt = [0 for i in range(k)] for x in a: for i in range(k): if (x & (1 << i)) == 0: cnt[i] += 1 ans2 = 0 for i in range(k): ans2 = (ans2 + (cnt[i] * cnt[i] + (n - cnt[i]) * (n - cnt[i])) * pow(2, i * 2, MOD)) % MOD ans2 = ans2 * 2 % MOD for i in range(k): for j in range(k): if i == j: continue ans2 = (ans2 + n * n * pow(2, i + j, MOD)) % MOD ans2 = ans2 * pow(2, 2 * (k - 1)) % MOD ans2 = (ans2 + MOD - ans1 * ans1 % MOD) % MOD print(ans2)