问题2152--数字串(num)

2152: 数字串(num)

时间限制: 1 Sec  内存限制: 512 MB
提交: 6  解决: 2
[提交] [状态] [讨论版] [命题人:]

题目描述

小学生zzq学习了平方数的概念之后,定义了一个新的概念平方串。
我们定义一个串为平方串当且仅当这个串非空而且它可以由两个相同串连接而成。例如naivenaive和aaaaaa为平方串,而naiveevian和aaaaa不是。
现在zzq拿到了一个很长的数字串(每个字符为0~9),他想要随机地取出一个非空子串,如果这个子串没有前导零且为平方串,那么它的价值就为它的数值,否则它的价值为0。例如015和233的价值为0,1515的价值为1515。
zzq想知道他取出子串价值的期望,mod 666623333输出。
如果答案是一个分数p/q,你需要输出一个数x使得qx≡p(mod 666623333)。

输入

一行一个数字串。

输出

一个整数,取出子串价值的期望mod 666623333。
样例解释
有三个子串价值非0,分别为”11”、”11”、”110110”,总共有36种选择子串的方案,所以子串价值的期望为(11+11+110110)/36=110132/36≡592557133。

样例输入 Copy

01101100

样例输出 Copy

592557133

来源/分类