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;
}