• Bạn có thể sử dụng phương pháp Sinh/Quay lui hoặc dùng hàm next_permutation có sẵn để có thể sinh ra đủ $$$n!$$$ hoán vị.

• Sau đó, ta chỉ cần kiểm tra xem số đầu tiên có phải số $$$m$$$ hay không, nếu đúng thì ta sẽ in ra hoán vị đó.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

int n, m, p[15], used[15];
void ql(int id){
    for(int i=1; i<=n; i++){
        if(!used[i]){
            used[i] = 1;
            p[id] = i;
            if(id == n){
                for(int j=1; j<=n; j++) cout << p[j] << ' '; cout << el;
            }else if(p[1] == m) ql(id + 1);
            used[i] = 0;
        }
    }
}

void solve(){
    cin >> n >> m;
    ql(1);
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Bạn có thể sử dụng phương pháp Sinh/Quay lui hoặc dùng hàm next_permutation có sẵn để có thể sinh ra đủ $$$n!$$$ hoán vị.

• Sau đó, nếu phần tử cuối cùng của hoán vị đúng là tên đề bài yêu cầu thì ta nhét hoán vị đó vào set để in ra theo thứ tự từ điển.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

void solve(){
    int n; cin >> n;
    string a[n+1];
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    string s; cin >> s;
    int p[n+1];
    for(int i=1; i<=n; i++) p[i] = i;
    set<string> se;
    do{
        if(a[p[n]] == s){
            string str = "";
            for(int i=1; i<=n; i++){
                str += a[p[i]] + " ";
            }
            se.insert(str);
        }
    }while(next_permutation(p+1, p+n+1));
    for(auto &i : se) cout << i << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Bạn có thể sử dụng phương pháp Sinh/Quay lui hoặc dùng hàm next_permutation có sẵn để có thể sinh ra đủ $$$n!$$$ hoán vị.

• Sau đó, nếu số đầu tiên lớn hơn số cuối cùng thì ta sẽ in ra hoán vị đó.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
 
void solve(){
    int n; cin >> n;
    vector<int> v;
    for(int i=1; i<=n; i++) v.push_back(i);
    do{
        if(v[0] > v[n - 1]){
            for(int &i : v) cout << i << ' '; cout << el;
        }
    }while(next_permutation(v.begin(), v.end()));
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Quay lui như bài tổ hợp chập $$$k$$$ của $$$n$$$, sau đó với mỗi trạng thái nối đủ $$$k$$$ số khác nhau, ta sẽ nhét trạng thái đó vào $$$set$$$ do không được in trùng và phải liệt kê theo thứ tự từ điển.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

int n, k, x[20];
string a[20];
set<string> s;
 
void run(int id){
    for(int i=x[id-1]+1; i<=n-k+id; i++){
        x[id] = i;
        if(id == k){
            string tmp = "";
            for(int j=1; j<=k; j++) tmp += a[x[j]];
            s.insert(tmp);
        }else run(id + 1);
    }
}
 
void solve(){
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    run(1);
    for(auto &i : s) cout << i << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Quay lui tạo ra các dãy con của mảng $$$a$$$, tức là chỉ số của phần tử đứng sau phải lớn hơn chỉ số của phần tử đứng trước. Ngoài ra, có thể thêm nhánh cận rằng nếu tổng hiện tại cộng thêm $$$a_i$$$ vẫn chưa vượt quá $$$s$$$ thì mới tiếp tục.

• Trường hợp $$$s = 0$$$, ta sẽ không được lấy dãy con rỗng, do đó cần xét kỹ ở trường hợp này.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

int n, s, a[22], res;
 
void run(int pos, int sum){
    if(sum == s and pos > 1) ++res;
    for(int i=pos; i<=n; i++){
        if(sum + a[i] <= s){
            run(i + 1, sum + a[i]);
        }
    }
}
 
void solve(){
    cin >> n >> s;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    run(1, 0);
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Kiểm tra tổng tất cả phần tử tỏng mảng $$$sum$$$ có chia hết cho $$$k$$$ hay không ? Nếu không chia hết, thì đáp án bài toán là $$$-1$$$.

Ta sẽ đặt một biến là tổng cần có của mỗi dãy con được tạo ra, có giá trị là $$$sum / k$$$. Sau đó quay lui tạo ra các dãy con của $$$a$$$, mỗi khi lấy một phần tử nào đó thì đánh dấu, xét xong thì xoá dấu. Ngoài ra, sử dụng thêm một biến $$$id$$$ dùng để đánh dấu số thứ tự nhóm đang có.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

int n, k, a[21], aim, f[21];
bool used[21];
 
bool run(int pos, int sum, int id){
    if(id > k) return 1;
    for(int i=pos; i<=n-k+id; i++){
        if(!used[i]){
            used[i] = 1;
            f[i] = id;
            sum += a[i];
            if(sum < aim){
                if(run(i + 1, sum, id)) return 1;
            }else if(sum == aim){
                if(run(1, 0, id + 1)) return 1;
            }
            used[i] = 0;
            sum -= a[i];
        }
    }return 0;
}
 
void solve(){
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        aim += a[i];
    }
    if(aim % k){
        cout << -1;
        return;
    }
    aim /= k;
    if(run(1, 0, 1)){
        for(int i=1; i<=n; i++){
            cout << f[i] << ' ';
        }
    }else cout << "-1";
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Cách $$$1$$$: bạn có thể sử dụng stack hoặc string để xử lý, lặp tới chừng nào $$$n = 0$$$, đưa số dư vào biến rồi sau đó in ngược lại.

• Cách $$$2$$$: sử dụng đệ quy, trường hợp cơ sở sẽ là $$$n = 0$$$ thì ta sẽ không in gì, nếu $$$n \neq 0$$$ thì ta sẽ gọi tới hàm $$$n / 2$$$ rồi sau đó mới in ra số dư của $$$n$$$ chia cho $$$2$$$. Tuy nhiên, trường hợp $$$n = 0$$$ ngay từ đầu thì ta sẽ phải in ra $$$0$$$ luôn.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

void run(int n){
    if(!n) return;
    run(n / 2);
    cout << n % 2;
}
 
void solve(){
    int n; cin >> n;
    if(!n) cout << 0;
    else run(n);
    cout << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

Ta sẽ sinh ra các dãy ngoặc bất kỳ giống như sinh xâu nhị phân, rồi sau đó kiểm tra tính đúng và in ra kết quả.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

bool check(string a){
    stack<char> st;
    for(char &c : a){
        if(c == '('){
            st.push(c);
        }else{
            if(st.empty()) return 0;
            st.pop();
        }
    }return st.empty();
}
 
void solve(){
    int n; cin >> n;
    n *= 2;
    queue<string> q;
    q.push("(");
    vector<string> v;
    while(!q.empty()){
        string s = q.front(); q.pop();
        if(s.size() == n and check(s)) v.push_back(s);
        if(s.size() < n){
            q.push(s + "(");
            q.push(s + ")");
        }
    }
    cout << v.size() << el;
    for(auto &i : v) cout << i << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Cách $$$1$$$: do giới hạn $$$n$$$ khá là bé, nên ta hoàn toàn có thể xét các vị trí $$$i$$$ trong đoạn $$$[1, j]$$$. Tuy nhiên, để có thể tính tổng một cách nhanh chóng thì ta sẽ cần sử dụng thêm mảng cộng dồn.

• Cách $$$2$$$: sử dụng chia để trị (tìm kiếm nhị phân), do $$$i$$$ càng gần $$$j$$$ thì tổng sẽ càng nhỏ nên ta sẽ sử dụng được thuật tìm kiếm này.

• Ta sẽ tính trước độ dài và số lượng kí tự a mà mỗi xâu $$$f_n$$$ đang quản lý.

• Với mỗi xâu $$$f_n$$$, ta sẽ phải xét đến $$$3$$$ vị trí như sau:

• Nếu $$$k$$$ đúng bằng độ dài xâu $$$f_n$$$ thì ta sẽ trả về luôn số lượng ký tự a trong xâu đó.

• Nếu $$$k$$$ lớn hơn độ dài xâu $$$f_{n - 1}$$$, tức là ta sẽ phải cộng toàn bộ số lượng ký tự a trong xâu $$$f_{n - 1}$$$ rồi ta lùi về xâu $$$f_{n - 2}$$$ rồi tính tiếp, nhưng chỉ số $$$k$$$ ta sẽ phải giảm đi $$$1$$$ lượng bằng độ dài xâu $$$f_{n - 1}$$$.

• Cuối cùng, $$$k$$$ nằm trong đoạn mà xâu $$$f_{n - 1}$$$ quản lý, thì ta chỉ việc lùi về xâu $$$f_{n - 1}$$$ và tính tiếp.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

int len[50], f[50];
void pre(){
    len[0] = len[1] = 1;
    f[0] = 1; f[1] = 0;
    for(int i=2; i<=45; i++){
        len[i] = len[i - 1] + len[i - 2];
        f[i] = f[i - 1] + f[i - 2];
    }
}
 
int solve(int n, int k){
    if(k == len[n]) return f[n];
    if(k > len[n - 1]) return f[n - 1] + solve(n - 2, k - len[n - 1]);
    return solve(n - 1, k);
}
 
void solve(){
    int n, k; cin >> n >> k;
    cout << solve(n, k) << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    pre();
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Đầu tiên, ta cần tạo một mảng lưu độ dài xâu: $$$len_i = |f_i|$$$. Với mỗi xâu $$$f_i$$$ = $$$f_{i - 1} + 1 + f_{i - 2}$$$ ta sẽ có $$$3$$$ vị trí $$$k$$$ cần phải xét đến như sau:

• $$$k$$$ nằm trong đoạn mà $$$f_{i - 1}$$$ quản lý, lúc đó ta chỉ cần tìm tiếp vị trí thứ $$$k$$$ ở xâu $$$f_{i - 1}$$$.

• $$$k$$$ nằm ngay sau đoạn mà $$$f_{i - 1}$$$ quản lý, tức là chỉ có thể là ký tự L hoặc V, lúc này ta dựa vào công thức đề để tìm đáp án.

• $$$k$$$ nằm trong đoạn mà $$$f_{i - 2}$$$ quản lý, lúc đó ta cần tìm tiếp ở xâu $$$f_{i - 2}$$$ nhưng ở vị trí nào ? Ta nhận thấy rằng ta phải giảm bớt $$$k$$$ xuống một lượng bằng nguyên đoạn đằng trước, tức là $$$k - len[i - 1] - 1$$$.

• Cuối cùng, khi xâu cần tìm ở vị trí $$$1$$$ hoặc $$$2$$$, ta sẽ giải quyết được bài toán.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

int len[90];
void prepare(){
    len[1] = len[2] = 1;
    for(int i=3; i<=88; i++) len[i] = len[i - 1] + 1 + len[i - 2];
}
 
char kitu(int n, int k){
    if(n == 1) return 'L';
    if(n == 2) return 'V';
    if(k == len[n - 1] + 1){
        if(n % 2 == 1) return 'L';
        return 'V';
    }
    if(k <= len[n - 1]) return kitu(n - 1, k);
    return kitu(n - 2, k - len[n - 1] - 1);
}
 
void solve(){
    int n, k; cin >> n >> k;
    cout << kitu(n, k) << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    prepare();
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

Để tính được $$$a^n$$$, ta sẽ cần đi tính trước giá trị $$$a^{n / 2}$$$ rồi sau đó bình phương lên, nếu $$$n$$$ là số lẻ thì ta nhân thêm $$$a$$$ vào. Như vậy, ta sẽ gọi hàm tính $$$a^{n / 2}$$$ đến khi gặp trường hợp cơ sở là $$$a^0 = 1$$$ và $$$a^1 = a$$$.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define int long long
#define mod 1000000007

int mu(int a, int b){
    if(b == 0) return 1;
    if(b == 1) return a;
    int tmp = mu(a, b / 2);
    int res = (tmp * tmp) % mod;
    if(b % 2) res *= a;
    return res % mod;
}

void solve(){
    int a, b; cin >> a >> b;
    cout << mu(a, b) << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Cách làm tương tự như bản $$$1$$$, tuy nhiên ta sẽ gặp phải một vấn đề như sau đó chính là thao tác nhân kể cả $$$2$$$ số sau khi đã được chia dư cho $$$c$$$ vẫn có thể gây ra tràn số $$$\to$$$ ta sẽ phải sử dụng chia để trị lần nữa để xử lý phép nhân này.

• Tư duy cũng giống với phép toán mũ, để tính được $$$a \times b$$$, ta sẽ cần tính trước $$$a \times (b / 2)$$$ và nếu $$$b$$$ là số lẻ thì ta cộng thêm $$$1$$$ số $$$a$$$ vào nữa. Trường hợp cơ sở sẽ là $$$a \times 0 = 0$$$ và $$$a \times 1 = a$$$.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define int long long

int mul(int a, int b, int c){
    int res = 0;
    while(b){
        if(b & 1) res = (res + a) % c;
        b /= 2; a = (a + a) % c;
    }return res;
}
 
int cal(int a, int b, int c){
    int res = 1;
    while(b){
        if(b & 1) res = mul(res, a, c);
        b /= 2; a = mul(a, a, c);
    }return res;
}

void solve(){
    int a, b, c; cin >> a >> b >> c;
    cout << cal(a, b, c) << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

• Về cơ bản thì đây là bài toán xử lý $$$a^b$$$ chia dư cho 10^6$, tuy nhiên đề bài lại yêu cầu bạn phải in ra đủ $$$6$$$ chữ số cuối cùng trong đáp án. Như vậy nếu cứ mod liên tục để lấy đáp án thì ta sẽ gặp tình trạng $$$10^6$$$ chia dư cho $$$10^6$$$ cho ra kết quả là $$$0$$$ mặc dù $$$1000000$$$ có $$$7$$$ chữ số $$$\to$$$ ta phải in ra $$$000000$$$ mới chính xác.

• Dựa vào đó, ta sẽ cần kiểm tra trước khi mod cho $$$10^6$$$ thì số đó đã $$$\geq 10^6$$$ hay chưa, nếu rồi thì ta sẽ cần in ra số dư đó với việc chèn thêm các số $$$0$$$ vào đầu cho đủ $$$6$$$ chữ số.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define int long long
#define mod 1000000

bool check;
int ltnp(int a, int b){
    int res = 1;
    while(b){
        if(a >= mod){
            a %= mod;
            check = 1;
        }
        if(b % 2){
            res *= a;
            if(res >= mod){
                res %= mod;
                check = 1;
            }
        }
        b /= 2;
        a *= a;
    }return res;
}
 
void solve(){
    int a, b; cin >> a >> b;
    int res = ltnp(a, b);
    if(check){
        string s = to_string(res);
        while(s.size() < 6) s = "0" + s;
        cout << s;
    }else cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

• Ta sẽ quay lui giống theo dãy con $$$a$$$ có $$$k$$$ phần tử có tổng bằng $$$c$$$, và với điều kiện đề bài thì các dãy được tạo ra không tăng, tức là $$$a_i \le a_{i - 1}$$$ với $$$2 \le i \le k$$$.

• Vì các khả năng có thể chia được kẹo là một mảng giảm dần, nên ta sẽ quay lui theo từng vị trí trong mảng, với các khả năng sẽ là $$$min(a_{i - 1}, x) \to 1$$$ với $$$x$$$ là số kẹo còn lại.

• Ta sẽ duy trì thêm một biến $$$opt$$$ để lưu giá trị nhỏ nhất của người được nhiều và ít kẹo nhất, cùng với đó là một mảng lưu trạng thái tối ưu. Chừng nào chúng ta chia được hết số kẹo, tức là số kẹo còn lại có thể đưa được hết cho người thứ $$$n$$$ thì ta sẽ cập nhật kết quả.

#include<bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#define len(x) (int)x.size()
#define set(a, x) memset(a, x, sizeof(a))
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

int n, c; // 2 biến đề cho
int cnt, opt; // cnt: số cách chia | opt: chênh lệch tối ưu
int cur[30], f[30]; // cur: trạng thái khi quay lui | f: phương án tối ưu

void run(int id, int c){ // xét vị trí id trong trạng thái với số kẹo còn lại là c
    // duyệt các khả năng
    for(int i=min(cur[id - 1], c); i>=1; i--){
        cur[id] = i;
        // trạng thái đã được tạo xong
        if(id == n){
            // kiểm tra trạng thái và cập nhật kết quả
            if(c == i){
                ++cnt;
                if(cur[1] - cur[n] < opt){
                    opt = cur[1] - cur[n];
                    for(int i=1; i<=n; i++) f[i] = cur[i];
                }
            }
        }else run(id + 1, c - i);
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);

    cin >> n >> c;
    cur[0] = opt = oo;
    run(1, c);
    cout << cnt << el;
    for(int i=1; i<=n; i++) cout << f[i] << ' ';
}

• Ý tưởng của bài toán được xuất phát từ nhận xét rằng $$$ax^3 + bx - c$$$ là hàm đồng biến. Như vậy, việc áp dụng tìm kiếm nhị phân trên hàm này là hoàn toàn khả thi. Trường hợp $$$a = 1, c = 10^6$$$ sẽ cho ra kết quả $$$x$$$ có thể lên tới $$$10^2$$$, do đó ta cần chặt trên đoạn $$$[1, 100]$$$.

• Tuy nhiên, để làm việc với số thực một cách chính xác nhất, ta nên sử dụng kiểu dữ liệu double cùng với đó là một số $$$epsilon$$$ đủ nhỏ để coi như $$$2$$$ số có chênh lệch $$$< epsilon$$$ là bằng nhau.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

double a, b, c;
double cal(double x){
    return a * x * x * x + b * x - c;
}
 
void solve(){
    cin >> a >> b >> c;
    double res = 0, l = 0, r = 100.0;
    while(r - l >= 1e-9){
        double mid = (l + r) / 2;
        if(cal(mid) <= 1e-9){
            res = mid;
            l = mid;
        }else r = mid;
    }
    cout << fixed << setprecision(4) << res << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

Nếu $$$n$$$ là số lẻ thì: $$$a^0 + a^1 + a^2 + ... + a^n$$$

$$$= (a^0 + a^1 + ... + a^{n / 2}) + a^{n / 2 + 1} \times (a^0 + a^1 + ... + a^{n / 2})$$$.

$$$= (a^0 + a^1 + ... + a^{n / 2}) \times (a^{n / 2 + 1} + 1)$$$.

Nếu $$$n$$$ là số chẵn thì: $$$a^0 + a^1 + a^2 + ... + a^n$$$

$$$= (a^0 + a^1 + ... + a^{n / 2 - 1}) + a^{n / 2} \times (a^0 + a^1 + ... + a^{n / 2 - 1}) + a^n$$$.

$$$= (a^0 + a^1 + ... + a^{n / 2 - 1}) \times (a^{n / 2} + 1) + a^n$$$.

#include<bits/stdc++.h>
using namespace std;

#define int long long

int mu(int a, int b, int m){
    int res = 1;
    while(b){
        a %= m;
        if(b & 1) res = res * a % m;
        a *= a; b >>= 1;
    }return res;
}

int cal(int a, int n, int m){
    if(n == 0) return 1;
    if(n % 2){
        int tmp = cal(a, n / 2, m);
        return (tmp + mu(a, n / 2 + 1, m) * tmp) % m;
    }else{
        int tmp = cal(a, n / 2 - 1, m);
        return (tmp + mu(a, n / 2, m) * tmp + mu(a, n, m)) % m;
    }
}

void solve(){
    int a, n, m; cin >> a >> n >> m;
    cout << cal(a, n, m);
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}