結果

問題 No.462 6日知らずのコンピュータ
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:20:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 2,432 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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()
0