VOJ - CP

Source: CP
Tags: Dynamic Programming, Checking by Probability

Problem:
Với mỗi chuỗi, tìm số lượng cách tách chuỗi đã cho thành nhiều chuỗi con sao cho mỗi chuỗi con là một số chính phương và không bắt đầu bằng số 0.
Dòng đầu tiên là số lượng test.
Các dòng sau là một chuỗi tương ứng với một test, độ dài chuỗi không quá 100.

Ví dụ:
Input:
1
169

Output:
2

Explanation:
Có 2 cách:
Để nguyên chuỗi ta có 169 = 13^2
Tách thành 16 = 4^2 và 9 = 3^2

Solution:
Bài này chỉ là một bài DP cơ bản, ta có công thức sau:
F[i] = tổng(F[j]) với j = 0..i - 1 thỏa S[j + 1..i] là một số chính phương.
Cái khó và quan trọng nhất ở bài này là phần kiểm tra chính phương.
Nhiều người có thể sẽ try hard cài Big Num và Binary Search để tìm căn, nhưng mà cách này không khả thi. Trong lúc Binary Search với mỗi lượt kiểm tra sẽ mất O(|S|) để cộng xâu, chia 2, trừ 1... và mất O(|S|^2) để bình phương lên kiểm tra (hoặc O(|S|^1.5) với hàm nhân Karatsuba), Binary Search là O(log(1e50)) và DP là O(|S|^2) vậy độ phức tạp tổng cộng sẽ là O(|S|^4*log(1e50)).
Vậy làm sao để giảm độ phức tạp của hàm kiểm tra? Ta có thể giải quyết bằng một hàm xác suất:
Gọi tập Y chứa những giá trị T^2 % X với mọi T. Ta chứng minh được rằng lực lượng của tập Y không vượt quá X / 2 + 1.
Với mỗi số T < X, ta có thể biểu diễn T thành T = X - k hoặc T = k với 0 ≤ k  ≤ X / 2.
Với cách biểu diễn T = X - k, ta có:
(X - k)^2 % X
= (X^2 - 2 * X * k + k^2) % X
= k^2 % X
Với cách biểu diễn T = k, ta có:
k^2 % X
Vậy số lượng của tập Y phụ thuộc vào số lượng k^2 % X, mà 0 ≤ k ≤ X / 2 do đó lực lượng tập Y có tối đa X / 2 + 1 phần tử.
Với mỗi số T ≥ X, ta có thể đưa về trường hợp T < X bằng cách gán T = T % X, về tính chất toán học thì như nhau vì T^2 % X = (T % X)^2 % X.
Gọi số cần kiểm tra là M. Ta có xác suất sai để M không chính phương nhưng M % X thuộc tập Y là 1 / 2. Ta kiểm tra với nhiều X sẽ giảm xác suất sai này xuống đáng kể.
Với mỗi X, ta dựng tập Y bằng mảng lùa trong O(X), lấy X random trong khoảng 2e4 ta có thể tạo 20 tập Y với 20 số X random tương ứng, độ phức tạp là O(4e5). Sau đó DP trong O(|S|^2) và kiểm tra trong O(20). Độ phức tạp tổng cộng là O(20|S|^2 + 4e5) với xác suất sai là 1 / 2 ^ 20.

À output các test đảm bảo trong giới hạn int64 :v

Code: (do |S| chỉ có 100 nên mình lười xài mảng nhớ mà với mỗi lần kiểm tra for lại lần nữa nên độ phức tạp là O(20|S|^3) :v)
#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

int x[20];
bool mark[20][20000];

void init() {
    srand(time(0));
    for (int i = 0; i < 20; ++i) {
        x[i] = rand() % 20000 + 1;
        for (int j = 1; j <= x[i]; ++j)
            mark[i][j * j % x[i]] = true;
    }
}

bool square(string t) {
    if (t[0] == '0')
        return false;
    for (int k = 0; k < 20; ++k) {
        int s = 0;
        for (int i = 0; i < t.length(); ++i)
            s = (s * 10 + t[i] - 48) % x[k];
        if (!mark[k][s]) return false;
    }
    return true;
}

int main() {
    init();
    int q; cin >> q;
    for (string s; q--;) {
        cin >> s;
        int n = s.length();
        s = ' ' + s;
        long long f[115];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            f[i] = 0;
            string t = "";
            for (int j = i; j; --j)
                if (square(t = s[j] + t))
                    f[i] += f[j - 1];
        }
        cout << f[n] << '\n';
    }
}