#AGC020E. [AGC020E] Encoding Subsets
[AGC020E] Encoding Subsets
题目描述
次のような、0
と 1
からなる文字列をエンコードする規則を考えます。
- 文字列
0
、1
はそれぞれ0
、1
とエンコードできる。 - 文字列 、 をそれぞれ 、 とエンコードできる場合、文字列 を とエンコードできる。
- 文字列 を とエンコードできる場合、 を正の整数として、文字列 ( を 個連結したもの)を
(
x
)
とエンコードできる。
例えば、文字列 001001001
は 001001001
、00(1(0x2)x2)1
、(001x3)
などとエンコードすることができ、この他のエンコード方法も存在します。
また、次の条件が満たされるとき、文字列 は文字列 の サブセット であると呼びます。
- と は長さが等しく、どちらも
0
と1
からなる。 - =
1
であるようなすべての添字 に対して、 =1
でもある。
0
と 1
からなる文字列 が与えられます。 のすべてのサブセットについて、それぞれをエンコードする方法が何通り存在するか求め、それらの個数の総和を で割ったあまりを求めてください。
输入格式
入力は標準入力から以下の形式で与えられる。
输出格式
のすべてのサブセットについてのエンコード方法の個数の総和を で割ったあまりを出力せよ。
题目大意
我们定义一个 01
串的压缩是满足如下方式的字符串变化过程:
- 如果 合法,那么 也合法(其中 代表字符串拼接)
- 如果 ,那么 也合法(其中
(
,)
,×
为字符, 为数字,算作一个字符,即使其中有 )
我们同时定义 串 是 的子集当且仅当:
现在给你一个 串 ,问它所有的子集的合法变化结果数的总和为多少。
答案对 取模。
011
9
0000
10
101110
156
001110111010110001100000100111
363383189
提示
制約
- は
0
と1
からなる。
Sample Explanation 1
のサブセットは 個存在し、 - 011
は 011
、0(1x2)
とエンコードできます。 - 010
は 010
とエンコードできます。 - 001
は 001
、(0x2)1
とエンコードできます。 - 000
は 000
、0(0x2)
、(0x2)0
、(0x3)
とエンコードできます。 したがって、 のすべてのサブセットについてのエンコード方法の個数の総和は 通りです。
Sample Explanation 2
今回は のサブセットは 個しか存在しませんが、 通りの方法でエンコードできます。
Sample Explanation 4
結果を で割ったあまりを出力することを忘れずに。