結果
問題 |
No.462 6日知らずのコンピュータ
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:20:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 2,432 bytes |
コンパイル時間 | 213 ms |
コンパイル使用メモリ | 82,060 KB |
実行使用メモリ | 54,560 KB |
最終ジャッジ日時 | 2025-03-31 17:20:49 |
合計ジャッジ時間 | 6,237 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 84 |
ソースコード
MOD = 10**9 + 7 def main(): import sys input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 k = int(input[ptr]) ptr += 1 # Precompute factorials up to 60! mod MOD max_fact = 60 fact = [1] * (max_fact + 1) for i in range(1, max_fact + 1): fact[i] = fact[i - 1] * i % MOD if k == 0: print(fact[N]) return a_list = list(map(int, input[ptr:ptr + k])) # Compute popcount for each a and check duplicates m_list = [] a_info = [] for a in a_list: m = bin(a).count('1') a_info.append((m, a)) m_list.append(m) # Check if all m are unique if len(set(m_list)) != k: print(0) return # Sort by m a_info.sort() m_sorted = [ai[0] for ai in a_info] a_sorted = [ai[1] for ai in a_info] prev_bits = 0 answer = 1 for i in range(k): current_a = a_sorted[i] current_m = m_sorted[i] current_bits = current_a # Check if current_bits has exactly current_m bits set if bin(current_bits).count('1') != current_m: print(0) return if i == 0: # Check for the first element: its bits should be exactly current_m prev_m = 0 diff_bits = current_bits ^ prev_bits cnt = bin(diff_bits).count('1') if cnt != current_m: print(0) return answer = answer * fact[current_m] % MOD else: prev_a = a_sorted[i - 1] prev_m = m_sorted[i - 1] # Check if prev_bits is subset of current_bits if (current_bits & prev_bits) != prev_bits: print(0) return # Calculate the number of differing bits (should be current_m - prev_m) diff = current_bits ^ prev_bits cnt = bin(diff).count('1') expected = current_m - prev_m if cnt != expected: print(0) return answer = answer * fact[expected] % MOD prev_bits = current_bits prev_m = current_m # Handle remaining bits remaining = N - prev_m if remaining < 0: print(0) return answer = answer * fact[remaining] % MOD print(answer) if __name__ == '__main__': main()