結果
| 問題 | No.3145 Astral Parentheses Sequence |
| ユーザー |
 magurofly
|
| 提出日時 | 2025-05-16 22:35:31 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 6,230 bytes |
| コンパイル時間 | 12,753 ms |
| コンパイル使用メモリ | 379,136 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-05-16 22:35:52 |
| 合計ジャッジ時間 | 14,567 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 45 |
コンパイルメッセージ
warning: unnecessary parentheses around assigned value
--> src/main.rs:107:24
|
107 | let limit: usize = (limit);
| ^ ^
|
= note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
|
107 - let limit: usize = (limit);
107 + let limit: usize = limit;
|
warning: unnecessary parentheses around assigned value
--> src/main.rs:135:20
|
135 | let n: usize = (n);
| ^ ^
|
help: remove these parentheses
|
135 - let n: usize = (n);
135 + let n: usize = n;
|
warning: unnecessary parentheses around `return` value
--> src/main.rs:137:28
|
137 | if n % 2 == 0 { return (2); }
| ^ ^
|
help: remove these parentheses
|
137 - if n % 2 == 0 { return (2); }
137 + if n % 2 == 0 { return 2; }
|
warning: unnecessary parentheses around `return` value
--> src/main.rs:138:28
|
138 | if n % 3 == 0 { return (3); }
| ^ ^
|
help: remove these parentheses
|
138 - if n % 3 == 0 { return (3); }
138 + if n % 3 == 0 { return 3; }
|
warning: unnecessary parentheses around `return` value
--> src/main.rs:139:28
|
139 | if n % 5 == 0 { return (5); }
| ^ ^
|
help: remove these parentheses
|
139 - if n % 5 == 0 { return (5); }
139 + if n % 5 == 0 { return 5; }
|
warning: unnecessary parentheses around block return value
--> src/main.rs:140:5
|
140 | (self.table[Self::index(n)])
| ^ ^
|
help: remove these parentheses
|
140 - (self.table[Self::index(n)])
140 + self.table[Self::index(n)]
|
ソースコード
#![allow(dead_code, unused_imports, unused_macros, non_snake_case)]
fn main() {
input! {
N: usize, M: usize,
}
if N % 3 != 0 {
say(0);
return;
}
let n = N / 3;
// binom(3n, n)/(2n+1)
let sieve = LinearSieve::new(3 * n + 1);
let mut pd = vec![0; 3 * n + 1];
for k in 1 ..= 3 * n {
for &(p, e) in &sieve.prime_division_pairs(k) {
pd[p] += e;
}
}
for k in 1 ..= n {
for &(p, e) in &sieve.prime_division_pairs(k) {
pd[p] -= e;
}
}
for k in 1 ..= 2 * n {
for &(p, e) in &sieve.prime_division_pairs(k) {
pd[p] -= e;
}
}
for &(p, e) in &sieve.prime_division_pairs(2 * n + 1) {
pd[p] -= e;
}
let mut ans = 1;
for p in 0 ..= 3 * n {
for _ in 0 .. pd[p] {
ans *= p;
ans %= M;
}
}
say(ans);
}
type Int = usize;
const MOD: Int = 998244353;
// const MOD: Int = 1_000_000_007;
const INF: Int = 1_000_000_000_000_000_000;
const YESNO: [&'static str; 2] = ["Yes", "No"];
use proconio::{input, input_interactive, marker::{Chars, Bytes, Usize1}};
use std::*;
use std::ops::*;
use collections::*; // (BTree|Hash)(Set|Map), BinaryHeap, VecDeque, LinkedList
use cmp::{self, Reverse}; // cmp::{min, max}
fn yes() { println!("{}", YESNO[0]); }
fn no() { println!("{}", YESNO[1]); }
fn yesno(c: bool) { println!("{}", if c { YESNO[0] } else { YESNO[1] }); }
fn say<T: std::fmt::Display>(x: T) -> T { println!("{}", x); x }
fn neighbor4<F: FnMut(usize, usize)>(i: usize, j: usize, h: usize, w: usize, mut f: F) { if i > 0 { (f)(i - 1, j); } if i < h - 1 { (f)(i + 1, j); } if j > 0 { (f)(i, j - 1); } if j < w - 1 { (f)(i, j + 1); } }
trait MyItertools : Iterator + Sized {
fn to_vec(self) -> Vec<Self::Item> { self.collect::<Vec<_>>() }
fn to_vec_rev(self) -> Vec<Self::Item> { let mut v = self.collect::<Vec<_>>(); v.reverse(); v }
fn tally(self) -> HashMap<Self::Item, usize> where Self::Item: Copy + Eq + hash::Hash { let mut counts = HashMap::new(); self.for_each(|item| *counts.entry(item).or_default() += 1 ); counts }
fn count_if<P: Fn(Self::Item) -> bool>(self, predicate: P) -> usize { self.map(predicate).filter(|&x| x ).count() }
fn implode(self, sep: &str) -> String where Self::Item: std::string::ToString { self.map(|x| x.to_string()).to_vec().join(sep) }
fn mex(self, gen: impl IntoIterator<Item = Self::Item>) -> Self::Item where Self::Item: Ord { let mut v = self.collect::<Vec<_>>(); v.sort(); v.dedup(); let mut it = v.into_iter(); gen.into_iter().find(|a| if let Some(x) = it.next() { a != &x } else { true }).unwrap() }
}
impl<T: ?Sized> MyItertools for T where T: Iterator + Sized {}
trait MyOrd : PartialOrd + Sized {
fn chmax(&mut self, mut rhs: Self) -> bool { if self < &mut rhs { *self = rhs; true } else { false } }
fn chmin(&mut self, mut rhs: Self) -> bool { if self > &mut rhs { *self = rhs; true } else { false } }
}
impl<T: Sized + PartialOrd> MyOrd for T {}
#[derive(Debug, Clone, Default)]
pub struct BTreeMultiset<T: Ord> { len: usize, set: BTreeMap<T, usize> }
impl<'a, T: Ord> BTreeMultiset<T> {
pub fn new() -> Self { Self { len: 0, set: BTreeMap::new() } }
pub fn len(&self) -> usize { self.len }
pub fn count(&self, x: &T) -> usize { self.set.get(x).copied().unwrap_or(0) }
pub fn insert_multiple(&mut self, x: T, count: usize) -> usize { self.len += count; let n = self.set.entry(x).or_insert(0); *n += count; *n }
pub fn insert(&mut self, x: T) -> usize { self.insert_multiple(x, 1) }
pub fn remove_multiple(&mut self, x: &T, count: usize) -> usize { if let Some(n) = self.set.get_mut(x) { let n0 = *n; *n = n0.saturating_sub(count); let n = *n; self.len -= n0 - n; if n == 0 { self.set.remove(x); } n } else { 0 } }
pub fn remove(&mut self, x: &T) -> usize { self.remove_multiple(x, 1) }
pub fn iter(&'a self) -> btree_map::Iter<'a, T, usize> { self.set.iter() }
pub fn into_iter(self) -> btree_map::IntoIter<T, usize> { self.set.into_iter() }
pub fn keys(&'a self) -> btree_map::Keys<'a, T, usize> { self.set.keys() }
pub fn range(&'a self, range: impl RangeBounds<T>) -> btree_map::Range<'a, T, usize> { self.set.range(range) }
}
type N = Int;
pub struct LinearSieve { limit: usize, primes: Vec<usize>, table: Vec<usize> }
impl LinearSieve {
const REM: [usize; 8] = [1, 7, 11, 13, 17, 19, 23, 29];
const IDX: [usize; 30] = [8, 0, 8, 8, 8, 8, 8, 1, 8, 8, 8, 2, 8, 3, 8, 8, 8, 4, 8, 5, 8, 8, 8, 6, 8, 8, 8, 8, 8, 7];
pub fn new(limit: N) -> Self {
let limit: usize = (limit);
let mut table = vec![1; (limit + 29) / 30 * 8 + 1];
let mut primes = Vec::with_capacity(32);
for i in 1 .. table.len() {
let n = 30 * (i >> 3) + Self::REM[i & 7];
if table[i] == 1 {
table[i] = n;
primes.push(n);
}
for &p in &primes {
if n * p > limit || p > table[i] {
break;
}
table[n * p / 30 << 3 | Self::IDX[n * p % 30]] = p;
}
}
Self { limit, table, primes }
}
pub fn is_prime(&self, n: N) -> bool {
let n: usize = n;
assert!(n <= self.limit);
n == 2 || n == 3 || n == 5 || n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && self.table[Self::index(n)] == n
}
pub fn primes(&self) -> Vec<N> { self.primes.iter().map(|&n| (n) ).collect::<Vec<_>>() }
pub fn least_prime_factor(&self, n: N) -> N {
let n: usize = (n);
assert!(n <= self.limit);
if n % 2 == 0 { return (2); }
if n % 3 == 0 { return (3); }
if n % 5 == 0 { return (5); }
(self.table[Self::index(n)])
}
pub fn prime_division(&self, mut n: N) -> Vec<N> {
assert!(n <= self.limit);
let mut divisors = vec![];
while n > 1 {
let d = self.least_prime_factor(n);
n /= d;
divisors.push(d);
}
divisors
}
pub fn prime_division_pairs(&self, n: N) -> Vec<(N, usize)> {
if n == 1 {
return vec![];
}
let pd = self.prime_division(n);
let mut prev_p = pd[0];
let mut e = 0;
let mut pairs = vec![];
for p in pd.into_iter().chain(Some(1)) {
if p == prev_p {
e += 1;
} else {
pairs.push((prev_p, e));
prev_p = p;
e = 1;
}
}
pairs
}
fn index(n: usize) -> usize { n / 30 << 3 | Self::IDX[n % 30] }
}