CF898F Restoring the Expression 题解

题意：

给你一个数字字符串s，现在你要这个字符串切割成三个部分a,b,c,
即s=a+b+c(这里的+为字符串相加，即后面的字符串拼接在前面的字符串后面)
同时要满足a，b，c三个字符串代表的十进制数字满足 a+b=c
(注意a,b,c都不能有前导0，如数字 0099 是非法的)
问是否有这样一种分隔方式,题目保证有一组解，输出+号最靠前的一组答案

输入一行一个字符串s,
输出一行，形如a+b=c，满足s=a+b+c（注意要输出'+'号和'='号）

|s|<=1e6,'0'<=si<='9'

input:
12345168
output:
123+45=168

~~模拟赛秒出结论，结果脑抽挂了。。~~

这题是字符串哈希，其实很好想

一般的字符串哈希函数都是这么定义的 \[ f(s[1\dots l])=\sum_{i=1}^{l} s[i]\times b^{l-i} \mod M \] 有没有觉得这个形式很熟悉？ \[ ax^3+bx^2+cx+d \] 如果 \(x=10\) ？我相信你一定明白了

这个字符串哈希的过程，

其实就是把这一段字符表示成了模 \(M\) 意义下的 \(x\) 进制数

因此，哈希，就没了。边界比较麻烦，要稍微处理一下

我们模拟赛没卡单哈，据说CF卡了那些经典素数，比如998244353和1e9+7

所以我就~~照着题解~~写了个双哈，模数是998244853和1e9+33

至于为什么要卡，因为 \(10\) 不是质数，冲突的概率会变大很多

时间复杂度 \(O(n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e6+15)

const int base=10;
const int mod1=998244853;
const int mod2=1e9+33;

char s[N];
int n,pos1,pos2,hsh[2][N],pwd[2][N];
int gethash1(int l,int r)
{
    int res=(hsh[0][r]-hsh[0][l-1]*pwd[0][r-l+1]%mod1)%mod1;
    res=(res+mod1)%mod1;
    return res;
}
int gethash2(int l,int r)
{
    int res=(hsh[1][r]-hsh[1][l-1]*pwd[1][r-l+1]%mod2)%mod2;
    res=(res+mod2)%mod2;
    return res;
}
bool check(int l,int r)
{
    if(s[l]!='0') return 1;
    for(int i=l+1; i<=r; i++)
        if(s[i]=='0') return 0;
    return 1;
}
bool checkr1(int len,int n,int flag)
{
    int l=n-(len<<1)+flag;
    if(l<1) return 0;
    return (((gethash1(1,l)+gethash1(l+1,n-len))%mod1==gethash1(n-len+1,n))&&check(l+1,n-len));
}
bool checkr2(int len,int n,int flag)
{
    int l=n-(len<<1)+flag;
    if(l<1) return 0;
    return (((gethash2(1,l)+gethash2(l+1,n-len))%mod2==gethash2(n-len+1,n))&&check(l+1,n-len));
}
bool checkl1(int len,int n,int flag)
{
    int l=len+flag-1;
    if(l<1) return 0;
    return (((gethash1(1,l)+gethash1(l+1,n-len))%mod1==gethash1(n-len+1,n))&&check(l+1,n-len));
}
bool checkl2(int len,int n,int flag)
{
    int l=len+flag-1;
    if(l<1) return 0;
    return (((gethash2(1,l)+gethash2(l+1,n-len))%mod2==gethash2(n-len+1,n))&&check(l+1,n-len));
}
void updater(int len,int flag)
{
    if(n-(len<<1)+flag<pos1) pos1=n-(len<<1)+flag,pos2=n-len;
}
void updatel(int len,int flag)
{
    if(len+flag-1<pos1)pos1=len+flag-1,pos2=n-len;
}
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+1); n=strlen(s+1);
    pwd[0][0]=pwd[1][0]=1; pos1=pos2=n;
    for(int i=1; i<=n; i++)
    {
        pwd[0][i]=pwd[0][i-1]*base%mod1;
        hsh[0][i]=(hsh[0][i-1]*base%mod1+s[i]-'0')%mod1;
        pwd[1][i]=pwd[1][i-1]*base%mod2;
        hsh[1][i]=(hsh[1][i-1]*base%mod2+s[i]-'0')%mod2;
    }
    for(int len=n/3; len<=(n>>1); ++len)
    {
        if(!check(n-len+1,n)) continue;
        if(checkr1(len,n,0)&&checkr2(len,n,0)) updater(len,0);
		if(checkr1(len,n,1)&&checkr2(len,n,1)) updater(len,1);
		if(checkl1(len,n,0)&&checkl2(len,n,0)) updatel(len,0);
		if(checkl1(len,n,1)&&checkl2(len,n,1)) updatel(len,1);
    }
    for(int i=1; i<=pos1; i++) cout << s[i];
    cout << '+';
    for(int i=pos1+1; i<=pos2; i++) cout << s[i];
    cout << '=';
    for(int i=pos2+1; i<=n; i++) cout << s[i];
    cout << '\n';
    return 0;
}