We know that by means of extended euclidean algorithm x and y can be calculated from ax + by = gcd(a, b). The formula is:

x = prev_y;
y = prev_x - (a/b) * x;

and the code is:

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

But in case of multiple integers, for instance, ax + by + cz = gcd(a, b, c), what will be the approach and code?

The output for "AABC" should be like this: AABC, AACB, ABAC, ABCA, ACAB, ACBA, BAAC, BACA, BCAA, CAAB, CABA, CBAA.

But the output of my code doesn't match with above. Can anyone find my where is the problem?

My Code

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

void permute(char str[], int count[], char result[], int level){
	if(level == strlen(result)){
		cout << result << "\n";
		return;
	}
	for(int i=0; i<strlen(str); i++){
		if(count[i] == 0) continue;
		result[level] = str[i];
		count[i]--;
		permute(str, count, result, level+1);
		count[i]++;
	}
}
int main(){
	char str[] = "AABC";
	int n = strlen(str);

	int cnt[n] = {0};

	for(int i=0; i<n; i++){
		int index = (str[i] - 'A');
		cnt[index]++;
	}

	char result[n];
	permute(str, cnt, result, 0);

	return 0;
}

The output of my code: AAA, AAB, AAA, AAB, ABA, ABA, AAA, AAB, ABA, BAA, BAA, BAA,

Could anyone please tell me how to get the traveled path for Traveling Salesman Problem?

My code is here:

int TSP(int i, int mask){
	if(mask == (1<<n)-1) return w[i][0];
	if(mem[i][mask] != -1) return mem[i][mask];

	int ans = INF;
	for(int j=0; j<n; j++){
		if(w[i][j] == INF) continue;
		if( (mask & (1<<j)) == 0){
			int result = TSP(j, (mask | (1<<j)) ) + w[i][j];
			ans = min(ans, result);
		}
	}
	return mem[i][mask] = ans;
}

I was reading substring hash from this link. But I got confused in the bold lines below. Could anyone explain me with example?

Suppose we are given a string S, and given indices I and J. It is required to find the hash from the substring S [I..J].

By definition, we have:

H [I..J] = S [I] + S [I + 1] * P + S [I + 2] * P ^ 2 + ... + S [J] * P ^ (J-I)

where from:

H [I..J] * P [I] = S [I] * P [I] + ... + S [J] * P [J],
H [I..J] * P [I] = H [0..J] - H [0..I-1]

The only problem that arises is what you need to be able to divide by P [I]. In fact, it is not so simple. Since we compute the hash modulo 2 ^ 64, for division by P [I] we must find the inverse element to it in the field (for example, using the Euclidean Advanced Algorithm ), and multiply by this inverse element.

However, there is an easier way. In most cases, instead of dividing hashes by degrees P, you can, conversely, multiply them by these degrees.

Suppose you have two hashes: one multiplied by P [I], and the other by P[J]. If I <J, then multiply the first hash by P[J-I], otherwise, multiply the second hash by P [I-J]. Now we have brought hashes to one degree, and we can safely compare them.