結果
問題 | No.2709 1975 Powers |
ユーザー |
|
提出日時 | 2024-03-31 14:01:14 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 183 ms / 2,000 ms |
コード長 | 1,508 bytes |
コンパイル時間 | 14,627 ms |
コンパイル使用メモリ | 404,036 KB |
実行使用メモリ | 64,500 KB |
最終ジャッジ日時 | 2024-09-30 18:48:08 |
合計ジャッジ時間 | 20,118 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
use std::collections::HashMap; fn main() { let stdin = std::io::stdin(); let mut line = String::new(); stdin.read_line(&mut line).unwrap(); let line: Vec<&str> = line.split_whitespace().collect(); let n = line[0].parse::<usize>().unwrap(); let p = line[1].parse::<i64>().unwrap(); let q = line[2].parse::<i64>().unwrap(); let mut line = String::new(); stdin.read_line(&mut line).unwrap(); let mut a: Vec<usize> = line .split_whitespace() .map(|s| s.parse::<usize>().unwrap()) .collect(); // powの事前計算 mod_powのライブラリがないので… let mut pre_pow = vec![vec![0; 2_000_001]; 4]; for (i, val) in [10, 9, 7, 5].iter().enumerate() { pre_pow[i][0] = 1; for j in 1..2_000_001 { pre_pow[i][j] = (pre_pow[i][j - 1] * val) % p; } } a.sort(); let mut sum = 0; for b_i in 0..n { let mut left_side: HashMap<i64, i64> = HashMap::default(); for a_i in 0..b_i { // aを選択 let value = (pre_pow[0][a[a_i]] + pre_pow[1][a[b_i]]) % p; *left_side.entry(value).or_insert(0) += 1; } for c_i in b_i + 1..n { for d_i in c_i + 1..n { let value = (pre_pow[2][a[c_i]] + pre_pow[3][a[d_i]]) % p; if let Some(count) = left_side.get(&((q - value + p) % p)) { sum += count; } } } } println!("{}", sum); }