Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/rope>
- using namespace std;
- using namespace __gnu_cxx;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef unsigned int ui;
- typedef long double ld;
- typedef pair<ll, ll> ii;
- typedef pair<ii, ii> iii;
- ll MOD = 1e9 + 7;
- const ld E = 1e-7;
- #define null NULL
- #define ms(x) memset(x, 0, sizeof(x))
- #ifndef LOCAL
- #define endl "\n"
- #endif
- #ifndef LONG_LONG_MAX
- #define LONG_LONG_MAX LLONG_MAX
- #endif
- #define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- #define _read(x) freopen(x, "r", stdin)
- #define _write(x) freopen(x, "w", stdout)
- #define files(x) _read(x ".in"); _write(x ".out")
- #define filesdatsol(x) _read(x ".DAT"); _write(x ".SOL")
- #define output _write("output.txt")
- #define input _read("input.txt")
- #define prev time_prev
- #define M_PI acos(-1)
- #define remove tipa_remove
- #define left tipa_left
- #define right tipa_right
- #define next tipa_next
- #define mod % MOD
- #define y1 hello_world
- unsigned char ccc;
- bool _minus = false;
- template<typename T>
- inline T sqr(T t) {
- return (t * t);
- }
- inline void read(ll &n) {
- n = 0;
- _minus = false;
- while (true) {
- ccc = getchar();
- if (ccc == ' ' || ccc == '\n')
- break;
- if (ccc == '-') {
- _minus = true;
- continue;
- }
- n = n * 10 + ccc - '0';
- }
- if (_minus)
- n *= -1;
- }
- inline void read(int &n) {
- n = 0;
- _minus = false;
- while (true) {
- ccc = getchar();
- if (ccc == ' ' || ccc == '\n')
- break;
- if (ccc == '-') {
- _minus = true;
- continue;
- }
- n = n * 10 + ccc - '0';
- }
- if (_minus)
- n *= -1;
- }
- char wwww[19];
- int kkkk;
- inline void write(ll y) {
- long long x = y;
- kkkk = 0;
- if (x < 0) {
- putchar('-');
- x *= -1;
- }
- if (!x)
- ++kkkk, wwww[kkkk] = '0';
- else
- while (x) {
- ++kkkk;
- wwww[kkkk] = char(x % 10 + '0');
- x /= 10;
- }
- for (int i = kkkk; i >= 1; --i)
- putchar(wwww[i]);
- }
- #ifdef LOCAL
- //#define DEBUG
- #endif
- #ifdef DEBUG
- #define dbg if(1)
- #else
- #define dbg if(0)
- #endif
- const int MAX = 5e3 + 10;
- ll KEY = 1191;
- ll dp[MAX][MAX];
- string s;
- inline void upd(ll &a, ll b) {
- a += b;
- if (a >= MOD) {
- a -= MOD;
- }
- }
- ll _hash[MAX], h[MAX];
- ll get(int l, int r) {
- ll ans = h[r + 1];
- ans -= (h[l] * _hash[r - l + 1]) % MOD;
- if (ans < 0) {
- ans += MOD;
- }
- return ans;
- }
- bool check_1(int l1, int r1, int l2, int r2) {
- if (s[l1] != s[l2]) {
- return s[l1] < s[l2];
- }
- if (get(l1, r1) == get(l2, r2)) {
- return false;
- }
- while (l1 <= r1) {
- if (s[l1] != s[l2]) {
- return s[l1] < s[l2];
- }
- l1++, l2++;
- }
- return false;
- }
- bool check_2(int l1, int r1, int l2, int r2) {
- while (l1 <= r1) {
- if (s[l1] != s[l2]) {
- return s[l1] < s[l2];
- }
- l1++, l2++;
- }
- return false;
- }
- bool check(int l1, int r1, int l2, int r2) {
- return check_1(l1, r1, l2, r2);
- assert(s[l1] != '0');
- assert(s[l2] != '0');
- assert(r1 - l1 == r2 - l2);
- bool res = check_1(l1, r1, l2, r2);
- assert(res == check_2(l1, r1, l2, r2));
- return res;
- }
- int main() {
- sync;
- srand(time(NULL));
- cout.precision(3);
- cout << fixed;
- #ifdef LOCAL
- input;
- #else
- #endif
- int n;
- cin >> n;
- cin >> s;
- h[0] = 0;
- _hash[0] = 1;
- for(int i = 1; i <= n; i++) {
- h[i] = (h[i - 1] * KEY + s[i - 1]) % MOD;
- _hash[i] = (_hash[i - 1] * KEY) % MOD;
- }
- dp[0][0] = 1;
- for(int i = 0; i + 1 < n; i++) {
- for(int j = 0; j < n; j++) {
- if(dp[i][j]) {
- upd(dp[i + 1][j + 1], dp[i][j]);
- if(s[i + 1] == '0') {
- continue;
- }
- if(i + j + 1 < n) {
- if(check(i - j, i, i + 1, i + j + 1)) {
- upd(dp[i + j + 1][j], dp[i][j]);
- } else if(i + j + 2 < n) {
- upd(dp[i + j + 2][j + 1], dp[i][j]);
- }
- }
- }
- }
- }
- ll ans = 0;
- for(int j = 0; j < n; j++) {
- upd(ans, dp[n - 1][j]);
- }
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement