CF477D Dreamoon and Binary 题解

题意：

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

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

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

将 \(n\) 打印到已经打印的字符串的右边，如果 \(n>0\), 则不打印前导 \(0\) 。

将 \(n\) 自增 \(1\ (n \leftarrow n+1)\) 。

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

由于答案可能很大，请模 \(10^9+7\) 输出。

输入格式：

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

输出格式：

第一行输出理想操作序列的个数模 \(10^9+7\) 的值。

第二行输出最短的理想操作序列的长度模 \(10^9+7\) 的值。

记原串为 \(x=\left(s_0 s_1 \cdots s_{n-1}\right)_2\) ，长度为 \(l\) ，接着考虑怎么dp。

设 \(f_{i,j}\) 表示 \(s\) 的前 \(i\) 位中，当前的 \(n = s[j..i]\) 的理想操作序列的个数，则 \[ f_{i, j}=\left[s_j=1\right] \times \sum_{\substack{k<j \\ s[k . . j] \leq s[j . . i]}} f_{j, k} \] 设 \(g_{i,j}\) 表示 \(s\) 的前 \(i\) 位中，当前的 \(n = s[j..i]\) 的最短理想操作序列中操作1的个数，则 \[ g_{i, j}=\left[s_j=1\right] \times \left(\min _{\substack{k<j \\ s[k . . j] \leq s[j . . i]}}\left\{g_{j, k}\right\} + 1\right) \] 现在的复杂度是 \(\mathcal{O}(l^3)\) 的，于是考虑优化这个dp。~~其实这个不难想到~~，前缀和优化嘛 \[ F_{i, j}=\sum_{k=j}^{i-1} f_{i, k},~ G_{i,j} = \min_{j \le k \le i-1}g_{i,k} \] 则有 \(f_{i,j} = F_{j,k_0}\) 当 \(k_0\) 为最小的满足 \(s[k_0..j] \le s[j..i]\) 的 \(k_0\) ，\(G_{i,j}\) 同理。

判断 \(j-k=i-j\) 时的大小关系，只需要预处理 \(s\) 的任意两个后缀的最长公共前缀长度即可。

这样复杂度就讲到了 \(\mathcal{O}(l^2)\) 。第一问的答案是 \(\sum_{i = 0}^{l - 1}f_{l,i}\) ，第二问的答案需要仔细思考一下。

考虑任意一个使得 \(g_{l,i} < +\infty\) 的 \(i\) ，可以计算出其 \(n\) 即 \(n = s[i..l]\) ，然后加上 \(g_{l,i}\) 就是一个可行答案

显然当 \(l\) 较小时， \(n\) 的值会很大很大。不过容易证明当 \(n \ge 2^{31}\) 时，最小的操作个数一定当 \(n\) 最小时取到。

更严格的话其实是 \(n \ge 2^{17} > 5000\) ，也就是说最后一段分在 \(n-16\) 前增加的花费已经大于了 \(g\) 的最大值。

时间复杂度 \(\mathcal{O}(l^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
#define INF 0x7f7f7f7f
const ll mod = 1e9 + 7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(5e3 + 5))
typedef int imat[N][N];

char s[N];
int n = 0,cnt = 0,mn = INF,tmp;
imat lcp, f, g, F, G;
bool cmp(int k, int j)
{
    int L = lcp[k][j]; if(k + L >= j) return 1;
    return s[k + L] <= s[j + L];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> s; for(int i = 0; s[i]; i++) f[++n][0] = 1;
    for(int i = n - 1; ~i; i--)
        for(int j = n - 1; ~j; j--) lcp[i][j] = (s[i] == s[j] ? lcp[i + 1][j + 1] + 1 : 0);
    memset(g, 0x7f, sizeof(g)); memset(G, 0x7f, sizeof(G));
    for(int i = 1; i <= n; i++) G[i][0] = F[i][0] = g[i][0] = 1;
    for(int i = 2, k; i <= n; i++)
        for(int j = i - 1; ~j; j--)
        {
            if(s[j] == '1' && j)
            {
                k = (j << 1) - i; add(f[i][j], F[j][max(k + 1, 0)]);
                down(g[i][j], G[j][max(k + 1, 0)] + 1);
                if(k >= 0 && cmp(k, j))
                {
                    add(f[i][j], f[j][k]);
                    down(g[i][j], g[j][k] + 1);
                }
            }
            add(F[i][j] = F[i][j + 1], f[i][j]);
            down(G[i][j] = G[i][j + 1], g[i][j]);
        }
    for(int i = 0; i < n; i++) add(cnt, f[n][i]);
    for(int i = n - 1; ~i; i--)
    {
        if(tmp = 0, g[n][i] < INF)
        {
            for(int j = i; j < n; j++)
            {
                (tmp <<= 1) |= s[j] & 1;
                tmp >= mod ? tmp -= mod : 0;
            }
            add(tmp, g[n][i]);
            if(i < n - 30 && mn >= INF) { mn = tmp; break; }
            down(mn, tmp);
        }
    }
    cout << cnt << '\n' << mn << '\n';
    return 0;
}