問題一覧 > 通常問題

No.1085 桁和の桁和

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 143
作問者 : tyawanmusityawanmusi / テスター : QCFiumQCFium
8 ProblemId : 3693 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-11-14 19:09:30

お知らせ

6/20 1:23 コーナーケースを追加し、リジャッジを行いました。
8/12 17:28 制約違反のケースがありました(修正済み)

問題文

茶碗蒸しくんはある整数Sが書かれた紙を紙の神様から貰いました。
しかし、紙の一部が神様の威光のせいで見えません。
Sの見え方を表す文字列Tが与えられます。
Tの長さとSの長さは等しく、Tの各文字は0~9,?のいずれかです。
Ti文字目(1i|S|)は、?ならSi文字目が見えないことを表し、そうでなければSi文字目はTi文字目と同じです。

神様は茶碗蒸しくんに次のヒントを教えてくれました。
次の操作を2020061920200619回行った時、SDは等しい。

  • SSの桁和で置き換える
ありうるSの総数を109+7で割った余りを求めてください。
また、Sの1文字目が0であることがあります。

制約

  • 1|T|105
  • 0D9
  • Tのそれぞれの文字は0~9,?のいずれかである
  • Dは整数である

入力

T
D

1行目にはTが入力されます。
2行目にはDが入力されます。

出力

ありうるSの総数を109+7で割った余りを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
13?3
1
出力
1

S=1333のとき、S13331011となり、Dと等しくなります。
操作後のSDと等しくなるのはこの1通りのみです。

サンプル2
入力
123456789
0
出力
0

整数が全て見えている場合もあります。
また、答えが0となる場合もあります。

サンプル3
入力
012?
3
出力
2

Tの1文字目が0?になることもあります。

サンプル4
入力
1?2?3?4?5?6?7?8?9?0?
9
出力
111111105

答えを109+7で割った余りを出力してください。

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