传送门：https://codeforces.com/contest/1051/problem/E
题意：
把一个数分成许多小段，每一段的值在L和R间。问有多少种分法。
思路 ：
首先，需要快速处理出每个位子 ，最近和最远可以组合的区间。如何处理这个区间，由于时限比较紧张，可以用哈希的方法，因为是长度固定，所以可以用二分确定两端长度前缀，再比较大小的方法。当然哈希要用比较好的双哈希。
然后，我们可以从后往前dp，每个位子的答案 = 这个位子对应区间的值的和。
#include <algorithm> #include <iterator> #include <iostream> #include <cstring> #include <cstdlib> #include <iomanip> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <stack> #include <cmath> #include <queue> #include <list> #include <map> #include <set> #include <cassert> using namespace std; #define lson (l , mid , rt << 1) #define rson (mid + 1 , r , rt << 1 | 1) #define debug(x) cerr << #x << " = " << x << " "; #define pb push_back #define pq priority_queue typedef long long ll; typedef unsigned long long ull; //typedef __int128 bll; typedef pair<ll ,ll > pll; typedef pair<int ,int > pii; typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q //priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q #define fi first #define se second //#define endl ' ' #define OKC ios::sync_with_stdio(false);cin.tie(0) #define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行 #define REP(i , j , k) for(int i = j ; i < k ; ++i) #define max3(a,b,c) max(max(a,b), c); #define min3(a,b,c) min(min(a,b), c); //priority_queue<int ,vector<int>, greater<int> >que; const ll mos = 0x7FFFFFFF; //2147483647 const ll nmos = 0x80000000; //-2147483648 const int inf = 0x3f3f3f3f; const ll inff = 0x3f3f3f3f3f3f3f3f; //18 const int mod = 998244353; const double esp = 1e-8; const double PI=acos(-1.0); const double PHI=0.61803399; //黄金分割点 const double tPHI=0.38196601; template<typename T> inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x; } /*-----------------------showtime----------------------*/ const int maxn = 1e6+9; const int base = 37; const int base2 = 71; const int MOD = 1e9+7; //const ll MOD2 = 1e16+17; int dple[maxn],dpri[maxn]; int lenle,lenri; ll dp[maxn],sum[maxn]; struct hash { char s[maxn]; ll h1[maxn],qp1[maxn]; ull h2[maxn],qp2[maxn]; ll p1[maxn],p2[maxn],len,val1[maxn],val2[maxn]; void init() { h1[0]=val1[0]=0; qp1[0]=p1[0]=1; len=strlen(s+1); for(int i=1;i<=len;i++) { qp1[i]=(qp1[i-1]*base)%MOD; h1[i]=(h1[i-1]*base%MOD+s[i])%MOD; } h2[0]=val2[0]=0; qp2[0]=p2[0]=1; for(int i=1;i<=len;i++) { qp2[i]=(qp2[i-1]*base2); h2[i]=(h2[i-1]*base2+s[i]); } } ll get_hash1(int l,int r) { return ((h1[r]-h1[l-1]*qp1[r-l+1])%MOD +MOD )% MOD; } ull get_hash2(int l,int r) { return ((h2[r]-h2[l-1]*qp2[r-l+1])); } }A,L,R; bool checkle(int l1, int r1) { int le = l1, ri = r1; while(le <= ri){ int mid = (le + ri) >> 1; if(A.get_hash1(le,mid) == L.get_hash1(le-l1+1,mid-l1+1) && A.get_hash2(le,mid) == L.get_hash2(le-l1+1,mid-l1+1)){ le = mid+1; } else ri = mid - 1; } if(le == r1 + 1) return true; return A.s[le] >= L.s[le - l1 + 1]; } bool checkri(int l1,int r1) { int le = l1, ri = r1; while(le <= ri){ int mid = (le + ri) >> 1; if(A.get_hash1(le,mid) == R.get_hash1(le-l1+1,mid-l1+1) &&A.get_hash2(le,mid) == R.get_hash2(le-l1+1,mid-l1+1) ){ le = mid+1; } else ri = mid-1; } if(le == r1 + 1) return true; return A.s[le] <= R.s[le - l1 + 1]; } int main(){ scanf("%s%s%s", A.s + 1, L.s + 1,R.s + 1); A.init(); L.init(); R.init(); ll len = A.len; int n = len; lenle = L.len; lenri = R.len; for(int i=1; i<=n; i++){ int le = i, ri = n; dple[i] = -1; dpri[i] = -1; if(A.s[i] == '0') { if(L.s[1] == '0') dple[i] = i,dpri[i] = i; else dple[i] = -1,dpri[i] = -1; continue; } if(i + lenle - 1<= n && checkle(i, i + lenle - 1)) dple[i] = i + lenle - 1; else if(i + lenle<=n)dple[i] = i + lenle; if(i + lenri - 1<= n&& checkri(i, i + lenri -1)) dpri[i] = i + lenri - 1; else dpri[i] = min(n,i+lenri-2); } sum[n+1] = 1; for(int i=n; i>=1; i--){ int pl = dple[i] + 1,pr = dpri[i] + 1; dp[i] = ((sum[pl] - sum[pr + 1] ) % mod + mod )%mod; sum[i] = (sum[i+1] + dp[i]) % mod; } cout<<dp[1]<<endl; return 0; }