Module d

ABC 384 D - Repeated Sequence

refs: https://atcoder.jp/contests/abc384/tasks/abc384_d

解となる文字列が $N$ 項を部分文字列に含むたびに, その部分列の和は最初の $N$ 項の総和分増加する. これはどの部分列を取る場合に置いても同様になる.

もし長さ $N$ 未満の部分列で, その部分列の和が $S$ を最初の $N$ 項の総和で割った余りとなるものが存在する場合, その部分列の間に繰り返される $N$ 項を挟むことで, 総和を $S$ にすることができるため, この部分列が存在するかどうかのみ確認すれば良い. 長さ $N$ 未満の部分列の探索については, 最初の $N$ 項の後に繰り返される領域を考慮する必要がある.

部分列の和は累積和を求めておくことで, 高速に探索できる.

use proconio::input;

fn main() {
    input! {
        n: usize, s: usize,
        a: [usize; n],
    }

    let sum = a.iter().sum::<usize>();
    let t = s % sum;

    let b = a.repeat(2).iter().fold(vec![], |mut acc, &x| {
        match acc.last() {
            Some(&last) => acc.push(x + last),
            None => acc.push(x),
        }

        acc
    });

    for i in 0..b.len() {
        if b.binary_search(&(b[i] + t)).is_ok() {
            println!("Yes");
            return;
        }
    }

    println!("No");
}