← 返回题目列表

AtCoder · joisc2009_sequence

sequence. 序列

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

数列 (Sequence) - 原题 PDF 第 1 页
原题PDF第1页
可复制的 PDF 提取文本
Sequence: 数列


input ファイル“sequence.in”
output 標準出力
ソースファイルsequence.c/sequence.cpp
時間制限1 秒/ データ


 数列{An} は,A1 からAm が入力によって与えられ,i ≧m + 1 のとき,Ai = Ai−1+Ai−m を
みたす.この数列の第p 項から第q 項{Ap, . . . , Aq} に含まれる奇数の個数を求めよ.

Input. 入力ファイルはsequence.in である.1 行目にはm が書かれている.2 行目にはp が
書かれている.3 行目にはq が書かれている.i + 3 行目(1 ≦i ≦m)にはAi に対応する値が

書かれている.
  4 行目から3 + m 行目に書かれている値は非負整数であり,2 000 000 000 = 2 × 109 よりも小
さい.また,2 ≦m ≦24, 1 ≦p < q ≦260 である.p, q の値が32bit に収まらないことに注意

せよ.

Output. 出力は標準出力に行うこと.指定された範囲に含まれる奇数の数を表す整数を出力

せよ.

採点基準採点用データのうち,配点の30 % 分はq ≦1 000 000 = 106 を満たす.

 例1                     例2
   sequence.in 標準出力                   sequence.in 標準出力
   4            3                         3            0
   2                                      1
   8                                      100
   1                                      0
   2                                      0
   3                                      0
   4





                            数列–1/1