898F - Restoring the Expression
思路：字符串hash，base是10，事实证明对2e64取模会T（也许ull很费时），对1e9+7取模。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ull unsigned long long
#define mem(a,b) memset(a,b,sizeof(a)) const int N=1e6+;
const int base=;
const int MOD=1e9+;
ll h[N];
ll p[N];
int num[N];
string s;
void init(string s)
{
int l=s.size();
h[]=;
for(int i=;i<l;i++)
{
h[i+]=(h[i]*base+s[i]-'')%MOD;
}
p[]=;
for(int i=;i<=l;i++)p[i]=(p[i-]*base)%MOD;
}
ll get(int l,int r)
{
if(r-l+<=||l-<||r<)return ;
return ((h[r]-h[l-]*p[r-l+])%MOD+MOD)%MOD;
}
bool is(int l,int r)
{
if(l<||r>=s.size()-||l>=r)return false;
if((r-l>=&&s[l+]=='')||(s.size()>=r+&&s[r+]==''))return false;
mem(num,);
string s1=s.substr(,l+);
string s2=s.substr(l+,r-l);
string s3=s.substr(r+,s.size()-r-);
//cout<<s1<<' '<<s2<<' '<<s3<<endl;
if(s2.size()>s3.size()||s1.size()>s3.size())return false;
if(s1.size()<s2.size())swap(s1,s2);
int tot=;
for(int i=s3.size()-;i>=;i--)
{
if(tot<=s2.size())
{
int t=s1[s1.size()-tot]-''+s2[s2.size()-tot]-''+num[i];
if(t>=)
{
if(i==)return false;
num[i-]=t/;
num[i]=t=t%;
}
if(t!=s3[i]-'')return false;
}
else if(tot<=s1.size())
{
int t=s1[s1.size()-tot]-''+num[i];
if(t>=)
{
if(i==)return false;
num[i-]=t/;
num[i]=t=t%;
}
if(t!=s3[i]-'')return false;
}
else
{
if(num[i]>=)
{
if(i==)return false;
num[i-]=num[i]/;
num[i]=num[i]%;
}
if(num[i]!=s3[i]-'')return false;
}
tot++;
}
return true;
}
void solve(string s)
{
init(s);
int pos=,_pos=;
int l=s.size();
for(int i=l-;i>=;i--)
{
int t=l-i;
ll sumh=get(i+,l);
if((get(,t)+get(t+,i))%MOD==sumh){
pos=t-;
_pos=i-;
if(is(pos,_pos))break;
else pos=_pos=;
}
if((get(,t-)+get(t,i))%MOD==sumh){
pos=t-;
_pos=i-;
if(is(pos,_pos))break;
else pos=_pos=;
}
if((get(,i-t)+get(i-t+,i))%MOD==sumh){
pos=i-t-;
_pos=i-;
if(is(pos,_pos))break;
else pos=_pos=;
}
if((get(,i-t+)+get(i-t+,i))%MOD==sumh){
pos=i-t;
_pos=i-;
if(is(pos,_pos))break;
else pos=_pos=;
}
} for(int i=;i<=pos;i++)putchar(s[i]);
putchar('+');
for(int i=pos+;i<=_pos;i++)putchar(s[i]);
putchar('=');
for(int i=_pos+;i<l;i++)putchar(s[i]);
puts("");
//cout<<pos<<' '<<_pos<<endl;
//cout<<get(1,1)<<' '<<get(2,22)<<' '<<get(23,44)<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cin>>s;
solve(s);
return ;
}