No.493 とても長い数列と文字列(Long Long Sequence and a String)

レベル : / 実行時間制限 : 1ケース 0.800秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 21
作問者 : e869120e869120 / テスター : square1001square1001

1 ProblemId : 1313 / 出題時の順位表

問題文

以下のような数列を考えます。
f(1)={1}
f(2)={1,4,1}
f(3)={1,4,1,9,1,4,1}
f(n)=f(n-1) + $n^2$ + f(n-1)

そのような数列をつなげて文字列にすることを考えます。
例えば、f(3)の場合"1419141"、もし数列が{9,11,10}の場合"91110"になります。
そのとき、K,L,Rが与えられます。

そのとき、f(K)を文字列化したときのL文字目からR文字目までの数字の和と、積を求めなさい。
積の方のみ$1000000007$($10^9+7$)で割った余りを求めてください。
ただし、0が含まれると、普通なら積の答えは0になってしまって面白くないので、「0」は和・積の計算の時のみ「10」として扱う事にします。
なお、Rの値がf(K)を文字列化した時の文字数を超える場合、"-1"と出力すること。


ここにいくつか例を説明します。
例1:もしf(K)が"91110"で、L=2, R=5のとき、和は$1+1+1+10=13$で、積は$1*1*1*10=10$です。
例2:もしf(K)が"1419141"で、L=1,R=7のとき、和は$1+4+1+9+1+4+1=21$で、積は$1*4*1*9*1*4*1=144$です。
例3:もしf(K)が"7777777"で、L=4,R=5のとき、和は$7+7=14$で、積は$7*7=49$ですです。
ちなみに例1では、該当する部分は"1110"、例2では、該当する部分は"1419141"となります。例3では"77"です。

参考程度に、f(1)~f(5)を文字化した時の文字列は以下のようになります。
f(1)を文字化したとき⇒"1"
f(2)を文字化したとき⇒"141"
f(3)を文字化したとき⇒"1419141"
f(4)を文字化したとき⇒"1419141161419141"
f(5)を文字化したとき⇒"1419141161419141251419141161419141"

入力

K L R

・1≦K≦10^9
・1≦L≦R≦10^18

出力

1行に、f(K)を文字化した時のL文字目~R番目までの数字の和と、積を1000000007で割った余りを空白区切りで出力しなさい。
ただし、L,Rは1-indexedとします。

サンプル

サンプル1
入力
3 1 7
出力
21 144

問題文中の例ですでに説明されています。

サンプル2
入力
5 12 19
出力
24 360

12番目から19番目までの文字列は"19141251"、よって和は24、積は360です。

サンプル3
入力
10 510 515
出力
17 96

サンプル4
入力
10 1 2016
出力
-1

f(10)の数列から作った文字列の長さは、1151文字なので、2016文字目はありません。

提出ページヘ