結果

問題 No.641 Team Contest Estimation
ユーザー lam6er
提出日時 2025-03-20 20:44:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 145 ms / 2,000 ms
コード長 2,488 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 100,988 KB
最終ジャッジ日時 2025-03-20 20:44:09
合計ジャッジ時間 1,760 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 9
inv3 = pow(3, MOD-2, MOD)
inv6 = pow(6, MOD-2, MOD)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx +=1
    K = int(data[idx])
    idx +=1
    A = list(map(int, data[idx:idx+N]))
    
    if K == 0:
        sum_A = sum(a % MOD for a in A) % MOD
        part1_val = sum( (a * a) % MOD for a in A ) % MOD
        sum_part = (sum_A * sum_A - part1_val) % MOD
        part2_val = sum_part % MOD
        total_S2_over_x = (part1_val + part2_val) % MOD
        sigma_sq_4k = (total_S2_over_x * 1 - sum_A * sum_A) % MOD
        if sigma_sq_4k < 0:
            sigma_sq_4k += MOD
        
        print(sum_A % MOD)
        print(sigma_sq_4k % MOD)
        return
    
    # Compute mu_part
    pow_2k_minus_1 = (pow(2, K, MOD) - 1) % MOD
    pow_2k_1 = pow(2, K-1, MOD)
    mu_part = (N * pow_2k_1 % MOD) * pow_2k_minus_1 % MOD
    
    # Compute part1_val
    t1 = (pow(2, K, MOD) -1) % MOD
    t2 = pow(2, K, MOD) % MOD
    t3 = (pow(2, K+1, MOD) -1) % MOD
    sum_ysquared = t1 * t2 % MOD
    sum_ysquared = sum_ysquared * t3 % MOD
    sum_ysquared = sum_ysquared * inv6 % MOD
    part1_val = sum_ysquared * N % MOD
    
    # Compute same_part
    same_sum = 0
    for b in range(K):
        cnt = 0
        for a in A:
            if (a >> b) & 1:
                cnt +=1
        cnt %= MOD
        c = cnt
        term1 = (c * (c-1)) // 2 % MOD
        nc = (N - c) % MOD
        term2 = (nc * (nc-1)) // 2 % MOD
        equal_pairs = (term1 + term2) % MOD
        power_4b = pow(4, b, MOD)
        same_sum = (same_sum + equal_pairs * power_4b) % MOD
    
    pow_2k_1 = pow(2, K-1, MOD)
    same_part = same_sum * pow_2k_1 % MOD
    
    # Compute different_part
    term = (pow(2, K, MOD) -1) % MOD
    term = term * term % MOD
    term2 = (pow(4, K, MOD) -1) % MOD
    term2 = term2 * inv3 % MOD
    term_diff = (term - term2) % MOD
    if term_diff < 0:
        term_diff += MOD
    term_diff = term_diff * pow(2, K-2, MOD) % MOD
    c_n_2 = (N * (N-1) // 2) % MOD
    different_part = term_diff * c_n_2 % MOD
    
    part2_val = (2 * (same_part + different_part)) % MOD
    
    total_S2_over_x = (part1_val + part2_val) % MOD
    
    sigma_sq_4k = (total_S2_over_x * pow(2, K, MOD) % MOD) - (mu_part * mu_part % MOD)
    sigma_sq_4k %= MOD
    if sigma_sq_4k <0:
        sigma_sq_4k += MOD
    
    print(mu_part % MOD)
    print(sigma_sq_4k % MOD)

if __name__ == "__main__":
    main()
0