题意：给定一个长度<=5000的二进制字符串S，以及一个初始为0的n，有一下两种操作：
1. 输出n(n>=1并且为2进制形式输出)
2.n=n+1
每次选择一种操作。。
求：1.有多少方案能构成该字符串 (%(10^9+7))
2.最少需要多少次能构成该字符串(%(10^9+7))
思路：
对于第一问：
能容易想到O(n^3)的dp
f[i][j] += f[k][i-1](其中[k,j-1]构成的数<=[i, j]组成的数，并且i,k位置为'1')
但是这样时限上显然不够，因为比较大小太耗时间了。。
由于是01串，我们可以先预处理same[i][j]表示以i开头和以j开头的数字最多多少个相同的。。这样判断就可以O(1)了
对于第二问：
还是可以用dp。。
f[i][j]表示以j结尾，[i, j]为最后一个数时最少分为几段。。思路跟上面差不多。。
但是比较大小可能需要一点技巧。。
基于最后结尾的数多一位，那么add操作次数*2，那么也就是说当最后的数很大是（add>=|S|），越小的结尾的数越优
所以，对于最后结尾的数比较小的，直接算出来，因为答案不会很大。。
否则的话，直接找结尾的数最小的就是最优解了。
当然，也可以基于上面的结论直接贪心。。
code:
#include <bits/stdc++.h>
#define M 1000000007
#define Inf 0x3fffffff
using namespace std;
char s[];
int same[][], f[][], c[][]; inline void add(int& c, const int &a, const int& b){
c = a + b;
if (c >= M) c -= M;
} int bigger(const int& x, const int& y, const int& k){
if (y <= ) return ;
int len = same[y][x];
if (len >= k) return ;
return s[x+len] >= s[y+len];
} void solve(){
int n = strlen(s + );
for (int i = n; i >= ; --i)
for (int j = i; j <= n; ++j)
if (s[i] == s[j]) same[i][j] = same[i+][j+] + ;
else same[i][j] = ;
for (int i = ; i <= n; ++i)
f[][i] = ;
c[][] = f[][];
for (int i = ; i <= n; ++i){
for (int j = i; j > ; --j) if (s[j] == ''){
add(f[j][i], f[j][i], c[j-][min(i-j, j-)]);
if (bigger(j, j--(i-j), i-j+)){
// if (j == 11 && i == 17) printf("%d %d %d\n", j, j-1-(i-j), i-j+1);
add(f[j][i], f[j][i], f[j--(i-j)][j-]);
}
}
for (int j = i; j >= ; --j)
add(c[i][i-j+], c[i][i-j], f[j][i]);
}
int ans1 = ;
for (int i = ; i <= n; ++i)
add(ans1, ans1, f[i][n]);
for (int i = ; i <= n; ++i)
for (int j = i; j <= n; ++j) f[i][j] = Inf;
for (int i = ; i <= n; ++i)
f[][i] = ;
for (int i = ; i <= n; ++i)
for (int j = ; j <= n; ++j) c[i][j] = Inf;
c[][] = ;
for (int i = ; i <= n; ++i){
for (int j = i; j > ; --j) if (s[j] == ''){
f[j][i] = min(f[j][i], c[j-][min(i-j, j-)] + );
if (bigger(j, j--(i-j), i-j+))
f[j][i] = min(f[j][i], f[j--(i-j)][j-] + );
}
for (int j = i; j >= ; --j)
c[i][i-j+] = min(c[i][i-j], f[j][i]);
}
int ans2 = Inf, x;
for (int i = n; i >= ; --i) if (f[i][n] < Inf){
if (n - i > ) break;
x = ;
for (int j = i; j <= n; ++j)
x = (x << ) + s[j] - '';
ans2 = min(ans2, x+f[i][n]);
}
if (ans2==Inf)
for (int i = n-; i >= ; --i) if (f[i][n] < Inf){
x = ;
for (int j = i; j <= n; ++j){
x = (x << ) + s[j] - '';
if (x >= M) x-=M;
}
ans2 = (x + f[i][n]) % M;
break;
}
printf("%d\n%d\n", ans1, ans2 % M);
} int main(){
while (scanf("%s", s+) != EOF){
solve();
}
}