結果

問題 No.3070 Collecting Coins Speedrun 2
ユーザー NakLon131
提出日時 2025-03-22 16:10:54
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 2,270 bytes
コンパイル時間 13,126 ms
コンパイル使用メモリ 378,496 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-22 16:11:09
合計ジャッジ時間 14,977 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn main() {
    // 入力
    input!{
        n: usize,
        c: [i64; n],
    }

    // cを正、負、0に分ける
    let mut positive_cnt = 0;
    let mut negative_cnt = 0;
    let mut zero_cnt = 0;
    for cc in c {
        if cc > 0 { positive_cnt += 1;}
        else if cc == 0 { zero_cnt += 1;}
        else { negative_cnt += 1;}
    }

    let mut ans = 1;

    // 正方向のコインx個の取り方 (1*2^(x-1))
    if positive_cnt > 0 {
        let ret = mod_pow(2, positive_cnt-1, MOD93);
        ans *= ret; ans %= MOD93;
    }
    
    // 負方向のコインx個の取り方 (1*2^(x-1))
    if negative_cnt > 0 {
        let ret = mod_pow(2, negative_cnt-1, MOD93);
        ans *= ret; ans %= MOD93;
    }
    // 0位置にあるコインの取り方 0のみ1、正あり+1、負あり+1
    if zero_cnt == 1 {
        let mut multi = 1;
        if positive_cnt > 0 { multi += 1; }
        if negative_cnt > 0 { multi += 1; }
        ans *= multi; ans %= MOD93;
    }
    // 経路の選び方 正負がそれぞれ一つ以上なら2
    if positive_cnt > 0 && negative_cnt > 0 {
        ans *= 2; ans %= MOD93;
    }

    println!("{}", ans);
}

// 繰り返し二乗法
fn mod_pow(mut a: usize, mut b: usize, mods: usize) -> usize {
    let mut res = 1;
    while b > 0 {
        if b % 2 == 1 {
            res *= a;
            res %= mods;
        }
        a *= a;
        a %= mods;
        b >>= 1;
    }
    res
}

// const MOD17: usize = 1000000007;
const MOD93: usize = 998244353;
// const INF: usize = 1 << 60;
// let dx = vec![!0, 0, 1, 0]; // 上左下右
// let dy = vec![0, !0, 0, 1]; // 上左下右
// let d = vec!{(!0, 0), (0, !0), (1, 0), (0, 1)}; // 上左下右

#[allow(unused)]
use proconio::{input, marker::Chars, marker::Usize1};

#[allow(unused)]
use std::{
    mem::swap,
    cmp::min, cmp::max,
    cmp::Reverse,
    collections::HashSet, collections::BTreeSet,
    collections::HashMap, collections::BTreeMap,
    collections::BinaryHeap,
    collections::VecDeque,
    iter::FromIterator,
};
// 配列のスペース区切り出力
#[allow(unused)]
fn vec_print<T: std::fmt::Display>(vec: &Vec<T>) {
    let sz = vec.len();
    for i in 0..sz-1 {
        print!("{} ", vec[i]);
    }
    println!("{}", vec[sz-1]);
}
0