F - square1001の好きな回文数 (square1001's Favorite Palindrome) Editorial /

Time Limit: 4 sec / Memory Limit: 256 MB

リジャッジをしました。申し訳ございません。(01/24 22:16:18追記)

部分点のケースはあっていますが、sub2-3.txtが間違っていることが判明しました。消去し次第リジャッジを行います。(01/24 22:12:49追記)

問題文

square1001の部分文字列である「1001」は回文数である。

すなわち、その名前を付けた彼も回文数が好きであった。

ということで、E869120は彼に次のような問題を出した。

「a以上b以下の数がある。 その中で、cの倍数かつ各位の数字の和が dである回文数はいくつあるか。」

square1001は、普通に全探索して求めようとしたが、 a , bが相当大きいためできなかった。

その問題の答えをmod 10000で求めよ。

入力

入力は以下の形式で標準入力から与えられる。

a b c d

正整数a,b,c,dが 1 行に入力される。

出力

条件を満たす回文数の個数を1行に出力せよ。

制約

  • a＜b
  • 2≦|a|=|b|≦80 かつ |a|, |b|は2の倍数
  • 1≦c≦50
  • 1≦d≦720
  • a,bは回文数

ここで, |a|はaの桁数を表す。

部分点

1≦a,b≦10,000,000,000を満たすデータセットすべてに正解した場合は、 20点が与えられる。

残りのデータセットすべてに正解した場合、80点が与えられる。

入力例1

1001 9999 9 36

出力例1

1

「9999」が条件を満たす。

入力例2

1001 4004 49 20

出力例2

1

「3773」が条件を満たす。

入力例3

1000000001 9999999999 50 50

出力例3

0

「0」で終わる回文数は存在しない。

問題文担当者：E869120