問題一覧 > 通常問題

No.3516 Very Large Range Mod

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 16
作問者 : yu23578 / テスター : aa36 Yoyoyo8128 GaLLium Germanium32 yt142857
ProblemId : 13126 / yukicoder contest 497 聖光学院プログラミングコンテスト2026 day1 (順位表) / 自分の提出
問題文最終更新日: 2026-04-24 21:45:52
yukicoder contest 497 聖光学院プログラミングコンテスト2026 day1の他の問題:

問題文

正整数列 $A$ は長さ $N$ の正整数列 $B,C$ を用いて表されます。 $A$ の先頭 $B_1$ 項は $C_1$ 、続く $B_2$ 項は $C_2$ $\cdots$ 末尾の $B_N$ 項は $C_N$ です。

正整数列 $A$ の中に含まれる長さ $K$ の連続部分列の内、 $K$ 個の要素の和が $M$ の倍数であるものの個数を解答してください。

制約

  • $1 \le N \le 2 \times 10^5$
  • $1 \le B_i,C_i \le 10^9$
  • $1 \le K,M \le 10^9$
  • $K \le \sum_{i=1}^{N} B_i$

入力

$N\ K\ M$
$B_1\ B_2\ \cdots\ B_N$
$C_1\ C_2\ \cdots\ C_N$

出力

条件を満たす連続部分列の個数を出力してください。最後に改行してください。

サンプル

サンプル1
入力
3 2 6
2 2 1
3 2 4
出力
2

$A(=(3,3,2,2,4))$ の中に含まれる長さ $K(=2)$ の連続部分列は、
$(A_1,A_2) = (3,3)$
$(A_2,A_3) = (3,2)$
$(A_3,A_4) = (2,2)$
$(A_4,A_5) = (2,4)$ の $4$ つです。
連続部分列の要素の総和はそれぞれ $6,5,4,6$ となります。 $6$ の倍数は $2$ つあるので、 $2$ を出力してください。

サンプル2
入力
1 1 1
1000000000
1000000000
出力
1000000000

サンプル3
入力
5 5 5
1 1 1 1 1
1 1 1 1 1
出力
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。