Codeforces ラウンド #272 (ディビジョン 1)D(String DP)_html/css_WEB-ITnose

D. Dreamoon と Binary

テストごとの制限時間

2 秒

テストごとのメモリ制限

512 メガバイト

入力

標準入力

出力

標準出力

Dreamoon は、大きな整数 x が地面に書かれており、そのバイナリ形式を出力したいと考えています。 Dreamoon は、x をバイナリ形式に変換する部分を完了しました。次に、次の方法で出力します。

彼は整数 n?=?0 を持っており、次の 2 つの操作のみを任意の順序でそれぞれ無制限に実行できます:

1. n を先行ゼロなしのバイナリ形式で出力します。 、各印刷は前の印刷の右側に追加されます。
2. n を 1 ずつ増やします。

理想的なシーケンスを、先行ゼロなしで x のバイナリ表現を正常に印刷でき、印刷操作 (つまり、操作 1)。 Dreamoon は、異なる理想シーケンスが何個あるか、および最短の理想シーケンスの長さ (演算中) を知りたいと考えています。

答えは大きい可能性があるため、1000000007 (109?+?7) を法として出力してください。

を定義しましょう「1」と「2」の文字列としての理想的なシーケンスの文字列表現。文字列内の i 番目の文字は、実行された i 番目の操作と一致します。 2 つの理想的なシーケンスは、文字列表現が異なる場合、異なると呼ばれます。

入力

入力の 1 行には、先行ゼロなしで x (1?≤?x?25000) を表す 2 進整数が含まれます。

出力

出力の最初の行には、1000000007 (109?+?7) を法とする異なる理想シーケンスの数を表す整数が含まれます。

出力の 2 行目には、理想の最小長を表す整数が含まれます。シーケンス モジュロ 1000000007 (109?+?7).

サンプル テスト

入力

101

出力

16

入力

rree

出力

11010

注

最初のサンプルの場合、最も短く唯一の理想的なシーケンスは長さ 6 の «222221» です。

2 番目のサンプルには、3 つの理想的なシーケンス «21211»、«212222222221»、«222222222222222222222222221» があります。その中で最も短いものは長さ 5 です。

题意：RT

思路：就是求将原串分成多个数字，使得全数字从左往右不递减即，求方案数

dp[i][j] 表示以到j结尾の二进制数的总方案数

dp[i][j] + = dp[k][i-1] （その中kから i-1 の 2 番目の数は、i から j の 2 番目の数より小さいか等しい）

さらに 1 つの mi[i][j] を使用して、i から j の尾の 2 番目の数を表します

mi[i][j] = min(mi[k][i-1]+1)

注意一下细节即可