(Rまでの個数)-(L-1までの個数)と変形し、主客転倒で桁ごとの寄与を考えるところまでは公式解説と同じです。

例として \(S=\) 34 のとき、\(R=123456\) までの \(f(x)\) の和を考えます。

• ????34
  • ???? の部分に 0 以上 1234 未満を充てる \(1234\) 個
  • ???? の部分に 1234 を充てる \(1\) 個
• ???34*
  • ??? の部分に 0 以上 123 未満を、* の部分に 0 以上 9 以下の数を充てる \(123\times 10\) 個
  • ???の部分に 123 を、* の部分に 0 以上 9 以下を充てる \(10\) 個
• ??34**
  • ?? の部分に 0 以上 12 未満を、** の部分に 0 以上 99 以下の数を充てる、\(12\times 100\) 個
  • ?? の部分に 12 を、**の部分に 0 以上 56 以下を充てる \(57\) 個
• ?34***
  • ? の部分に 0 以上 1 未満を、*** の部分に 0 以上 999 以下の数を充てる、\(1\times 1000\) 個
  • ? の部分に 1 を充てることはできない
• 34****
  • (空文字列) の部分に 0 以上 0 未満を、**** の部分に 0 以上 9999 以下の数を充てる、\(0\times 10000\) 個
  • (空文字列) の部分に 0 を充てることはできない

このように、桁ごとに、「\(S\) にあたる部分より上位の桁で \(R\) 未満であることが確定するケース」「\(S\) にあたる部分より上位の桁が \(R\) と一致するケース」の 2 つに分けることでそれぞれ個数を求めることができます。

\(S\) の先頭が 0 の場合は、上位の ? が 0 になれないことに注意してください。

実装例(C++)