問題概要

周期 $N$ をもつ無限数列 $A$ の先頭 $N$ 項が与えられる。この数列の空でない連続する部分列のうち、和が $S$ となるものが存在するか判定せよ。

制約

入力はすべて整数。
$1\leq N\leq2\times10^5$
$1\leq A_i\leq 10^9$
$1 \leq S\leq 10^{18}$

考察

和が $S$ となる $A$ の連続部分数列を $B$ 、 $A$ の1周期分の数列を $C = (A_1, A_2, \cdots, A_N)$ とする。このとき、 $B$ は先頭から以下のようなグループに分けられる。

$A_i$ から $A_N$ の部分。
$C$ を $k \: (k \geq 0)$ 回以上繰り返した部分。すなわち、 $A_{N+1}$ から $A_{(k+2)N}$ の部分。
$A_1$ から $A_j$ の部分。

このうち、2番目の部分については、 $S \mod \displaystyle \sum C$ を取ることで無視することができる。

したがって、 $R = S \mod \displaystyle C$ とすれば、残りの部分は長さが $N$ 以下となり、この問題を以下のように言い換えることができる。

$A$ の長さ $N$ 以下の連続部分数列であって、総和が $R$ となるものを求めよ。

このパターンは2周期分の累積和を取るのが有効。すなわち、 $\mathrm{ps}_i = \displaystyle \sum_{1 \leq j \leq i} A_j \: (0 \leq i \leq 2N)$ とすれば、

数列 $\mathrm{ps}$ において、 $\mathrm{ps}_j - \mathrm{ps}_i = R \Leftrightarrow \mathrm{ps}_i + R = \mathrm{ps}_j$ を満たす組 $(i, j) \: (1 \leq i \leq N)$ が存在するか判定せよ。

と、上記の問題をさらに言い換えることができる。

これは $N$ の制約から愚直な線形探索は厳しいが、累積和の数列 $\mathrm{ps}$ が単調増加数列であることに注目すると、二分探索を使って $O(N \log N)$ で判定を行うことができる。

コード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N;
    ll S;
    cin >> N >> S;
    ll cycle_sum = 0;
    vector<ll> A(N * 2);
    rep(i, 0, N) cin >> A[i], A[i + N] = A[i], cycle_sum += A[i];

    ll remain = S % cycle_sum;

    vector<ll> ps(N * 2 + 1, 0);
    rep(i, 0, N * 2) ps[i + 1] = ps[i] + A[i];

    rep(i, 0, N)
    {
        if (binary_search(all(ps), ps[i] + remain))
        {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
}