一天，scx 在地上发现一个巨大的整数 $x$，然后想把它写成二进制形式。

scx 凭借她娴熟的技巧，将整数 $x$ 变成了它的二进制形式。现在，她想要用下列方式来打印这个数：

一开始，她有一个整数 $n = 0$，然后，她可以以任何顺序、次数没有限制地执行如下两种操作：

scx 认为，如果一串操作序列可以成功地打印出 (没有前导 $0$ 的) $x$ 且以操作 $1$ 结束，则这串操作序列是理想的。scx 想知道一共有多少种理想操作序列，以及最短的理想操作序列的长度。

输入格式

输入共一行，包含一个以二进制形式表达的正整数 $x$ ($x < 2^{50}$)。

输出格式

题解

记原串为 $x = (s_0 s_1 \cdots s_{l-1})_2$，长度为 $l$ ($l \leq 5000$)，记子串 $s_i s_{i+1} \cdots s_{j-1}$ 对应的数为 $s[i..j] = (s_i s_{i+1} \cdots s_{j-1})_2$。

那么如果令 $f_{i, j}$ 表示 $s$ 的前 $i$ 位中，当前的 $n = s[j..i]$ 的理想操作序列的个数，则有转移方程如下：

$$ f_{i, j} = [s_j = \texttt{1}] \cdot \sum_{\quad \ k < j \\ s[k..j] \leq s[j..i]} f_{j, k} $$

同理记 $g_{i, j}$ 表示 $s$ 的前 $i$ 位中，当前的 $n = s[j..i]$ 的最短的理想操作序列中打印操作的个数，则有转移方程如下：

$$ g_{i, j} = [s_j = \texttt{1}] \cdot \min_{\quad \ k < j \\ s[k..j] \leq s[j..i]} \{ g_{j, k} \} $$

，则有 $f_{i, j} = F_{j, k_0}$，其中 $k_0$ 为最小的满足 $s[k_0..j] \leq s[j..i]$ 的 $k_0$，$G_{i, j}$ 同理。

现在主要是判断 $j - k = i - j$ 时是否满足，这可以预处理出原串 $s$ 中任意两个后缀的最长公共前缀的长度，就可以通过 lcp[k][j] 来判断 ($k = 2j - i$)。

这样，时间复杂度就降到了 $O(l^2)$，第一问的答案就是 $\sum\limits_{i = 0}^{l - 1} f_{l, i}$，那第二问的答案呢？

考虑任意一个使得 $g_{l, i} < +\infty$ 的 $i$，可以计算出对应的 $n$ 值，即 $n = s[i..l]$，此即自增操作的个数，加上 $g_{l, i}$ 即为一种可行答案值。

当然，当 $l$ 较小时，$n$ 的值 (自增操作的个数) 可能会巨大，导致不取模无法存下，这时，可以证明，当 $n \geq 2^{32}$ 时，最少的操作个数一定是当 $n$ 最小时取到，用反证法易证。

代码

#include <bits/stdc++.h>
#define N 5003
#define INF 0x7f7f7f7f
#define count scx
using namespace std;

typedef int imat[N][N];
typedef long long ll;
const ll mod = 1000000007;

char s[N], *p = s + 1;
int n = 0, i, j, k;
int count, minimize, tmp;
imat lcp, f, g, F, G;

inline void down(int &x, const int y) {x > y ? x = y : x;}

inline bool cmp(int L, int M){
    int g = lcp[L][M]; if(L + g >= M) return true;
    return s[L + g] <= s[M + g];
}

int main(){
    scanf("%s", s);
    for(p = s; *p; ++p) f[++n][0] = 1;
    for(i = n - 1; ~i; --i)
        for(j = n - 1; ~j; --j)
            lcp[i][j] = (s[i] == s[j] ? lcp[i + 1][j + 1] + 1 : 0);
    memset(g, 127, sizeof g); memset(G, 127, sizeof G);
    for(i = 1; i <= n; ++i) G[i][0] = F[i][0] = g[i][0] = 1;
    for(i = 2; i <= n; ++i)
        for(j = i - 1; ~j; --j){
            if(s[j] == '1' && j){
                k = (j << 1) - i;
                (f[i][j] += F[j][max(k + 1, 0)]) >= mod ? f[i][j] -= mod : 0;\
                down(g[i][j], G[j][max(k + 1, 0)] + 1);
                if(k >= 0 && cmp(k, j)){
                    (f[i][j] += f[j][k]) >= mod ? f[i][j] -= mod : 0;
                    down(g[i][j], g[j][k] + 1);
                }
            }
            (F[i][j] = F[i][j + 1] + f[i][j]) >= mod ? F[i][j] -= mod : 0;
            G[i][j] = min(G[i][j + 1], g[i][j]);
        }
    count = 0;
    for(i = 0; i < n; ++i) (count += f[n][i]) >= mod ? count -= mod : 0;
    minimize = INF;
    for(i = n - 1; i >= 0; --i)
        if(g[n][i] < INF){
            tmp = 0;
            for(j = i; j < n; ++j){
                (tmp <<= 1) |= s[j] & 1;
                tmp >= mod ? tmp -= mod : 0;
            }
            (tmp += g[n][i]) >= mod ? g[n][i] -= mod : 0;
            if(i < n - 30 && minimize >= INF) {minimize = tmp; break;}
            down(minimize, tmp);
        }
    printf("%d\n%d\n", count, minimize);
    return 0;
}

坑

坑1：由于这题的数据规模较大，因此比较卡空间，因为 $5000 \times 5000$ 的 int 数组就要占 $96 \mathrm{MB}$，数组一共 $5$ 个，刚好 $480 \mathrm{MB}$，如果开 $5$ 个 long long 就要爆掉了。还有，如果分开算答案的话 (算完第一问重新算第二问)，可以节省两个大数组的空间。

题目描述

输入格式

输出格式

题解

代码

坑