Chlience

【题解】CF 1051E Vasya and Big Integers
Problem传送门 >ω<题目大意:给定一个数 $a$ ,求将其划分为任意个没有前导零的,大小在 $l,r$ 之...
扫描右侧二维码阅读全文
30
2018/10

【题解】CF 1051E Vasya and Big Integers

Problem

传送门 >ω<

题目大意:

给定一个数 $a$ ,求将其划分为任意个没有前导零的,大小在 $l,r$ 之间的数的方案数

这里的划分指在某些数位断开,如 $12345 = 1 + 2 + 3 + 45$

Solution

看到数据范围显然是需要 DP 的吧

$f[i]$ 表示前 $i$ 位被划分的方案数

那么可以往前找到最长的某段 $ll ,rr$ ,使得 $s_{ll} \cdots s_i \leq r$ 且 $l \leq s_{rr} \cdots s_i$

即找到以 $s[i]$ 结尾的符合条件的子串集合

显然有

for j = ll to rr
    f[i] += f[j]

或者考虑某个位置 $i$ 向后转移

即找到最长的某段 $ll , rr$ ,使得 $l \leq s_{i + 1} \cdots s_{ll}$ 且 $s_{i + 1} \cdots s_{rr} \leq r$

即找到以 $s[i + 1]$ 开头的符合条件的子串集合

显然有

for j = ll to rr
    f[j] += f[i]

关键在于求出 $ll , rr$

假设现在有两个很大的数字 $x , y$ ,询问你这两个数的大小关系

首先显然直接比较位数

其次比较第一位 到 最后一位

如果中间某一位不相同,则直接得到答案

若相同,则比较下一位

位数很好判断,接下来需要的就是求出那一位 不相同 的以比较大小

也就是两个串的最长公共前缀的后一位

在第一种情况下,因为仅仅确定了最后一位,那么前缀就会一直改变,不利于求公共前缀

反之第二种情况直接确定了第一位,那么所有的前缀已经确定,那么就直接和 $l , r$ 比较确定大小关系即可

即求 $s$ 的后缀与 $t$ 的前缀的匹配

总所周知的,使用扩展 $KMP$ 算法能够简单的解决这个问题

所以我们只要求出每次能够更新的区间 $[ll , rr]$ ,用前缀和实现区间加即可统计答案

接下来就是喜闻乐见的代码时间!(贼好打

我才不会告诉你之前打了个线段树结果挂了就是调不出来 qwq

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
const int mod = 998244353;
char str[N];
char s[2][N];
int nxt[2][N];
int extend[2][N];
void get_nxt(char *s , int *nxt) {
    int n = strlen(s) , r = 0 , pos = 1;
    nxt[0] = n;
    while(r + 1 < n && s[r] == s[r + 1]) ++ r;
    nxt[1] = r;
    for(int i = 2 ; i < n ; ++ i) {
        nxt[i] = max(0 , min(nxt[i - pos] , r - i + 1));
        while(i + nxt[i] < n && s[i + nxt[i]] == s[nxt[i]]) ++ nxt[i];
        if(i + nxt[i] - 1 > r) {
            r = i + nxt[i] - 1;
            pos = i;
        }
    }
}
void get_extend(char *s , char *t , int *nxt , int *extend) {
    int n = strlen(s) , m = strlen(t) , pos = 0 , r;
    while(s[extend[0]] == t[extend[0]]) ++ extend[0];
    r = extend[0] - 1;
    for(int i = 1 ; i < n ; ++ i) {
        extend[i] = max(0 , min(nxt[i - pos] , r - i + 1));
        while(i + extend[i] < n && extend[i] < m && s[i + extend[i]] ==  t[extend[i]]) ++ extend[i];
        if(i + extend[i] - 1 > r) {
            r = i + extend[i] - 1;
            pos = i;
        }
    }
}
int sum[N];
int now;
int main() {
    scanf("%s %s %s" , str , s[0] , s[1]);
    int len = strlen(str);
    int lenl = strlen(s[0]);
    int lenr = strlen(s[1]);
    int f = (lenl == 1 && s[0][0] == '0');//用来检测‘0’(合法)以及前导‘0’(不合法)
    get_nxt(s[0] , nxt[0]);
    get_nxt(s[1] , nxt[1]);
    get_extend(str , s[0] , nxt[0] , extend[0]);
    get_extend(str , s[1] , nxt[1] , extend[1]);
    int now = 1;
    sum[0] = mod - 1;
    for(int i = 0 ; i < len ; ++ i) {
        int l , r;
        if(str[i] == '0') {
            if(f) l = r = i;
            else {
                now = (now + sum[i]) % mod;
                continue;
            }
        }
        else {
            l = i + lenl - 1;
            if(extend[0][i] != lenl && s[0][extend[0][i]] > str[i + extend[0][i]]) ++ l;
            //确定左区间
            r = i + lenr - 1;
            if(extend[1][i] != lenr && (s[1][extend[1][i]] < str[i + extend[1][i]])) -- r;
            //确定右区间
        }

        sum[l] = (sum[l] + now) % mod;
        sum[r + 1] = (sum[r + 1] - now + mod) % mod;
        //更新后面答案
        now = (now + sum[i]) % mod;
        //更新当前答案
    }
    printf("%d\n" , now);
    return 0;
}
Last modification:October 30th, 2018 at 09:52 pm

Leave a Comment