SDE - 1

Step 1: Analyze Bit by Bit

Iterate through the bits from the most significant bit (n−1) down to 0. For each bit position i, there are two main scenarios for the bits of x and y at that position (xi​ and yi​):

Case 1: xi​==yi​
In this case, no matter what bit we choose for zi​, the resulting bits in A and B will be the same (xi​⊕zi​). To maximize the product, we want both numbers to be as large as possible. Therefore, we choose zi​ such that it flips the bits of x and y to 1.

If xi​=0, set zi​=1→ both become 1.

If xi​=1, set zi​=0→ both become 1.

Case 2: xi​=yi​
In this case, one of the resulting bits in A or B will be 1, and the other will be 0, regardless of whether we pick zi​=0 or zi​=1. This is where the "balancing" strategy comes in.

Step 2: The "First Difference" Strategy

The very first time we encounter Case 2 (xi​=yi​), we have a choice. To maximize the product, we should give this high-value bit (2i) to the number that is currently smaller.

If both are currently equal, give it to either one (let's say A).

Once one number (e.g., A) has "taken" a 1 at a higher bit, it is now strictly larger than B.

Step 3: Balance the Remaining Bits

For all subsequent instances of Case 2 (xj​=yj​ where jSince A is already larger than B due to the bit at position i, we should give all following 1 bits to B to keep the two numbers as close together as possible (minimizing their difference).

Set zj​ such that the bit in B becomes 1 and the bit in A becomes 0.

Step 4: Calculate the Final Product

After determining all bits of z, calculate A=(x⊕z) and B=(y⊕z). Compute (A⋅B)(mod109+7). Be careful to use long long for the multiplication before the modulo.

Step 1: Define the DP Table

Create a 2D array dp[i][j] where:

i represents the prefix of string s of length i.

j represents the prefix of string t of length j.

dp[i][j] stores the number of ways to form the prefix t[0…j−1] using characters from the prefix s[0…i−1].

Step 2: Initialize Base Cases

If t is empty: An empty string is a subsequence of any string exactly once. So, dp[i][0] = 1 for all i.

If s is empty (and t is not): You cannot form a non-empty string from an empty one. So, dp[0][j] = 0 for all j>0.

Step 3: Establish Transitions

Iterate through s from 1 to n and t from 1 to m. For each pair (i,j):

If s[i−1]=t[j−1]: The current character in s cannot be used to match the current character in t. We must carry over the count from the previous prefix of s:
dp[i][j]=dp[i−1][j]

If s[i−1]==t[j−1]: We have two choices:

Use s[i−1] to match t[j−1]: Look for the prefix t[0…j−2] in s[0…i−2] → dp[i-1][j-1].

Don't use s[i−1]: Look for the current prefix t[0…j−1] in the previous prefix s[0…i−2] → dp[i-1][j].

Total: dp[i][j]=(dp[i−1][j−1]+dp[i−1][j])(mod109+7).

Step 4: Space Optimization (Optional)

Since dp[i][j] only depends on the previous row (i-1), you can optimize the space to O(∣t∣) by using a 1D array and iterating backwards to avoid overwriting values from the current iteration.