Subtask 1

Trong quá trình thao tác, gọi một bước là bước lựa chọn nếu ta có thể ghép ~X~ và ~Y~ và được lựa chọn ghép hay không. Dễ dàng nhận thấy số lượng bước lựa chọn tối đa là ~n~, và ở mỗi bước lựa chọn ta có 2 thao tác con có thể lựa chọn. Vì thế, ta có thể sử dụng đệ quy quay lui để duyệt toàn bộ các cách thao tác khác nhau, rồi đếm số lượng dãy ~b~ khác nhau từ đó với độ phức tạp là ~O(n \cdot 2^n)~.

Subtask 2

Định nghĩa một dãy ~b~ là hợp lệ nếu nó có thể được tạo ra từ thao tác trong đề bài, và một cấu hình phản tế bào là hợp lệ nếu nó là một cấu hình có thể thu được từ thao tác trong đề bài. Ta có một số nhận xét sau:

• Mỗi dãy ~b~ hợp lệ cho ra một câu hình phản tế bào hợp lệ: Từ một dãy ~b~ hợp lệ bất kì, ta có thể đi dọc dãy ~b~ và chọn ghép ở những vị trị ~i~ tương ứng với phần tử trong ~b~, cuối cùng thu được một phản tế bào hợp lệ.
• Mỗi cấu hình phản tế bào hợp lệ cho ra một cách ghép hợp lệ: Vì ta chỉ có thể ghép 2 phản tế bào nếu chúng kế nhau và có cùng tổng, và vì mỗi phần tử được đảm bảo là dương, ta có thể suy ngược từ mỗi phản tế bào cuối cùng xem hai phản tế bào nào có thể ghép một cách hợp lệ ra nó, từ đó suy ra một cách ghép hợp lệ. Ví dụ, phản tế bào ~[1, 1, 2]~ chỉ có thể được tạo ra từ 2 phản tế bào ~[1, 1]~ và ~[2]~; phản tế bào ~[1, 1]~ lại chỉ có thể được tạo ra từ ~[1]~ và ~[1]~. Vì thế, ta có thể suy ra được là muốn tạo phản tế bào ~[1, 1, 2]~, đầu tiên ta phải ghép ~[1]~ với ~[1]~, sau đó là ~[1, 1]~ với ~[2]~.
• Mỗi cách ghép hợp lệ cho ra một dãy ~b~ hợp lệ: Đây là vì thao tác của chúng ta được định nghĩa với ~i~ không giảm, ta luôn phải chọn ghép bước ghép nằm ở "trái" nhất. Ví dụ, để tạo ra ~[1, 1], [2, 2]~, ta phải chọn ghép ~[1]~ và ~[1]~ trước, vì nếu chọn ghép ~[2]~ và ~[2]~ thì thao tác định nghĩa ở đề bài sẽ không cho phép chúng ta quay về ghép ~[1]~ và ~[1]~. Vì thế, chỉ có một chuỗi thao tác hợp lệ duy nhất tương ứng với mỗi cách ghép, tức có một dãy ~b~ duy nhất.

Ghép cả 3 nhận xét, ta thấy được mỗi dãy ~b~ hợp lệ tương ứng với một cấu hình phản tế bào và ngược lại, điều đó nghĩa là số lượng dãy ~b~ hợp lệ bằng số lượng cấu hình phản tế bào. Bài toán trở thành đếm số lượng cấu hình phản tế bào hợp lệ.

Ta sẽ làm quy hoạch động như sau: định nghĩa ~f_i~ là số lượng cấu hình phản tế bào hợp lệ khi chỉ thao tác lên ~i~ phần tử đầu của ~a~. Công thức quy hoạch động ta có thể thấy rõ: giả sử ~S_i~ là tập các vị trí ~j~ sao cho ~a_{j..i}~ có thể ghép thành một phản tế bào duy nhất, ta có ~f_i = \sum_{j \in S_i} f_{j - 1}~.

Nhận xét: ~a_{j..i}~ có thể ghép thành một phản tế bào duy nhất nếu tồn tại vị trí ~k~ sao cho ~a_{j..k}~ có thể ghép thành một phản tế bào duy nhất, ~a_{k+1..i}~ có thể ghép thành một phản tế bào duy nhất, và ~\sum(a_{j..k}) = \sum(a_{k+1..i})~. Nhận thấy tiếp là bởi vì nhận xét trên, ~k+1~ sẽ nằm trong ~S_i~, và ~j~ sẽ nằm trong ~S_k~, nên ta có thể lưu lại ~S_x~ cho mọi vị trí ~x < i~, rồi ta có thể tính được ~j~ bằng cách kiểm tra xem liệu có phần tử ~j~ nào trong ~S_k~ thoả mãn ~\sum(a_{j..k}) = \sum(a_{k+1..i})~ hay không, với ~k + 1~ là vị trí cuối cùng trong ~S_i~. Ta hoàn toàn cũng có thể chứng mình được ta có thể lưu lại toàn bộ các ~S~: vì ~\sum(a_{j..k}) = \sum(a_{k+1..i})~ nên ~\sum(a_{j..i}) = 2\sum(a_{k+1..i})~, vì thế tổng các phản tế bào kết thúc tại ~i~ sẽ gấp đôi dần, vậy nên ~|S_i|~ tối đa sẽ là ~\log(n \max_a)~. Việc lưu lại ~S~ bằng std::map hoặc std::set và làm quy hoạch động từ đó sẽ có độ phức tạp là ~O(n \log^2(n \max_a))~.

Bonus: Cải tiến lên ~O(n \log(n \max_a))~

Ta có thêm hai nhận xét sau:

• Tổng của các phản tế bào kết thúc tại ~i~ sẽ có dạng ~2^x a_{i}~ với ~x \ge 0~. Đây là vì tính chất gấp đôi dần của các phản tế bào kết thúc tại ~i~.
• Giả sử ~a_{j..k}~ và ~a_{k+1..i}~ là hai phản tế bào có thể ghép lại được với nhau, ta có ~a_k = 2^x a_i~. Đó là vì ~\sum(a_{j..k}) = 2^t a_k = \sum(a_{k+1..i}) = 2^z a_i~ nên ~a_k = 2^{z-t} a_i~.

Vì thế, ta hoàn toàn không cần phải lưu ~S~ bằng std::map hay std::set mà có thể lưu trong mảng, với ~S_i[x]~ biểu diễn vị trí ~k + 1~ sao cho ~a_{k + 1..i}~ ghép được thành phản tế bào và ~\sum(a_{k + 1..i}) = 2^x~. Để tính ~S_i[x+1]~, ta có thể tính nhanh ~\log{\frac{a_k}{a_i}}~ sử dụng __builtin_clzll hoặc __lg, rồi truy nhập vào vị trí đúng đắn của ~S_k~ để gán vào ~S_i[x+1]~.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9 + 7;

int n;
int a[200001];

int f[200001][61], val[200001][61];

int dp[200001];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        f[i][0] = i;
        val[i][0] = a[i];
    }   

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 60; j++) {
            int p = f[i][j - 1];
            if (p == 0 || p == 1 || val[i][j - 1] % a[p - 1] != 0) f[i][j] = 0;
            else {
                int tmp = val[i][j - 1] / a[p - 1];
                if (__builtin_popcountll(tmp) != 1 || f[p - 1][__builtin_ctzll(tmp)] == 0) f[i][j] = 0;
                else {
                    f[i][j] = f[p - 1][__builtin_ctzll(tmp)];
                    val[i][j] = val[i][j - 1] * 2;
                }
            }
        }

    dp[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= 60; j++)
            if (f[i][j])
                (dp[i] += dp[f[i][j] - 1]) %= mod;              
    cout << dp[n];
}