Number of Solutions to a Linear Algebraic Equation

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	adamant	157
6	awoo	157
8	TheScrasse	154
8	nor	154
10	djm03178	153

The Basic Problem

Suppose, we have a Linear Algebraic Equation, X₁ + X₂ + X₃ = 5. Here the values of X₁, X₂ and X₃ can be non-negative integers. We want to know in how many ways we can assign values to X₁, X₂ and X₃ so that the summation is 5.

We can consider this problem as dividing 5 objects among 3 persons. And below are some possible ways to do it —

Here by O the objects are being represented and | represents partition. As the objects are divided among 3 persons we need 2 partitions which is pretty clear from the partitioning instances above.

We can finalize this problem as simple combinatorial problem of number of ways of arranging 7 objects where 5 are of first kind and the other 2 are of second kind. And the answer is $\text{[math]}$ So if we have n objects in total and we want to divide those among k persons, we can do that in $\text{[math]}$ ways.

Adding Upper Bound

Now let's modify the above problem by a bit. Let's set upper bounds on the terms of the above equation. Suppose, X₁≤2, X₂≤ 1 and X₃≤ 3 and we want to know the number of solutions to the equation. In the result we calculated above there are some solutions where X₁ > 2 or X₂ > 1 or X₃ > 3. If we can figure out the number of invalid solutions and deduct it from the above result then we can get our desired result. Let's first figure out the number of solutions where X₁ > 2. We can simply deduct 3 from the total number of objects and give those to X₁ and then divide the rest of the objects among all the terms. In this way X₁ obviously exceeds its bound of 2. So solving the equation X₁ + X₂ + X₃ = 2, we get the number of solutions where X₁ exceeds its bound. Following the similar way we can find out the number of solutions where X₂ and X₃ exceeds their bounds. Then we can deduct all of these invalid solutions from the above result to remove the invalid results.

Now we've actually removed some invalid solutions more than once. When finding out the number of solutions where X₁ exceeds 2 and solving X₁ + X₂ + X₃ = 2, we've also removed the solutions where X₂ exceeds 1. And then again we've removed it separately for X₂. So same invalid configuration is actually removed twice and we have to add the number of solutions where both X₁ and X₂ exceeds their bounds to the above result. This is actually a classical Inclusion-Exclusion problem. If we choose odd number of terms and find out the numbers of solutions where they exceed bounds, we deduct it from the result and if we choose even number of terms and find out the numbers of solutions where they exceed bounds, we add it to the result. Finally we get the number of solutions where all the terms are under the bound.

Adding Lower Bound

Lastly consider that some lower bounds are set on the terms of the equation. Suppose, X₁ ≥ 1, X₂ ≥ 0 and X₃ ≥ 2 and we want to know the number of solutions to the equation. If you observe carefully you will notice that if we decrease the particular upper bounds by their lower bounds and reset them and also decrease the total number of objects by the summation of lower bounds then the problem is just similar to the previous problem of finding number of solutions with upper bounds. Now the number of solutions to the newly set equation is actually the numbers of solutions to a Linear Algebraic Equation with both upper and lower bounds.

Practice Problems

Problem Makes Problem This problem is quite similar to the basic problem discussed above.

Code

#include <bits/stdc++.h>

using namespace  std;

typedef long long ll;
const ll mod = 1000000007;

#define SZ 2000010

ll BigMod (ll B, ll P, ll M) {
    ll R = 1 % M;
    while (P > 0) {
        if(P % 2 == 1) {
            R = (R * B) % M;
        }
        P /= 2;
        B = (B * B) % M;
    }
    return R;
}

ll fact[SZ];

int main() {
    fact[0] = 1;
    for(ll i = 1; i<SZ; i++)
        fact[i] = (i * fact[i-1]) % mod;

    int t;
    scanf("%d",&t);

    for (int cs = 0; cs < t; cs++) {
        ll n, k;
        scanf("%lld %lld",&n,&k);

        ll ans = fact[n+k-1];
        ans = (ans * BigMod(fact[n], mod - 2, mod)) % mod;
        ans = (ans * BigMod(fact[k-1], mod - 2, mod)) % mod;

        printf("Case %d: %lld\n", cs + 1, ans);
    }

    return 0;
}

Cricket Ranking This problem is quite similar to the problem of solving Linear Algebraic Equation with upper and lower bounds discussed above.

Code

#include <bits/stdc++.h>

using namespace  std;

typedef long long ll;

const ll mod = 100000007;

#define SZ 1000000+10

ll BigMod (ll B, ll P, ll M) {
    ll R = 1 % M;
    while (P > 0) {
        if(P % 2 == 1) {
            R = (R * B) % M;
        }
        P /= 2;
        B = (B * B) % M;
    }
    return R;
}

ll nCr (int n, int r, vector <ll>& fact) {
    if(r > n) return 0LL;
    ll ans = fact[n];
    ans = (ans * BigMod(fact[r], mod-2, mod)) % mod;
    ans = (ans * BigMod(fact[n-r], mod-2, mod)) % mod;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);

    vector <ll> fact(1000001, 1);
    for (int i = 1; i <= 1000000; i++) {
        fact[i] = ((ll)i * fact[i-1]) % mod;
    }

    int t;
    cin >> t;

    for (int cs = 0; cs < t; cs++) {
        int k, n;
        cin >> k >> n;

        vector <int> low(k), high(k);

        for (int i = 0; i < k; i++) {
            cin >> low[i] >> high[i];
        }

        ll ans = 0LL;
        int lim = (1 << k);

        for (int mask = 0; mask < lim; mask++) {
            int tot = n, cnt = 0;

            for (int i = 0; i < k; i++) {
                if (mask & (1<<i)) {
                    tot -= (high[i] + 1);
                    cnt++;
                } else {
                    tot -= low[i];
                }
            }

            if (tot < 0) continue;

            if (cnt & 1) ans = ans - nCr(tot + k - 1, k - 1, fact);
            else ans = ans + nCr(tot + k - 1, k - 1, fact);

            if (ans < 0) ans += mod;
            if (ans >= mod) ans -= mod;
        }

        printf("Case %d: %lld\n", cs + 1, ans);
    }

    return 0;
}

Toph Biswa the Digital Gutibaj In this problem you also need to find the number of solutions to a Linear Algebraic Equation with upper and lower bounds. But here you can use as many terms as you want. So just choose some terms at each step and then solve for them. You also need to multiply the answer at each step with the factorial of number of terms chosen as the requirement of the problem. Here the number of objects can be as large as 10¹² but the number of terms is at most 10. You can simply iterate to find out the nCr value.

Code

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

const ll mod = 1E9 + 7;

ll f[12];
ll inv[12];

ll BigMod (ll B, ll P) {
    ll R = 1 % mod;
    while (P > 0) {
        if (P & 1) {
            R = (R * B) % mod;
        }
        P /= 2;
        B = (B * B) % mod;
    }
    return R;
}

ll nCr (ll n, int r) {
    if (r > n) return 0LL;
    if (n == r || r == 0) return 1LL;

    if (r > n-r)
        r = n-r;
    n %= mod;

    ll ans = 1LL;
    for (int i = 1; i <= r; i++) {
        ans = (ans * ((n - (ll)i + 1LL + mod) % mod)) % mod;
        ans = (ans * inv[i]) % mod;
    }

    return ans;
}

int main () {
    ios::sync_with_stdio(false);

    f[0] = 1;
    for (int i = 1; i <= 10; i++) {
        inv[i] = BigMod(i, mod - 2LL);
        f[i] = ((ll)i * f[i-1]) % mod;
    }

    int n;
    ll l;

    while (cin >> n >> l) {
        vector <ll> a(n);

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

        ll ans = 0;
        int lim = (1 << n);

        for (int taken = 1; taken < lim; taken++) {
            int k = __builtin_popcount(taken);

            vector <ll> v;
            for (int i = 0; i < n; i++) {
                if (taken & (1<<i)) {
                    v.push_back(a[i]);
                }
            }

            int tlim = (1 << k);

            for (int mask = 0; mask < tlim; mask++) {
                ll tot = l, cnt = 0;

                for (int i = 0; i < k; i++) {
                    if(mask & (1 << i)) {
                        tot -= (v[i] + 1);
                        cnt++;
                    } else {
                        tot -= 1;
                    }
                }

                if(tot < 0) continue;

                ll tmp = (nCr(tot+k-1, k-1) * f[k]) % mod;

                if(cnt & 1) ans = ans - tmp;
                else ans = ans + tmp;

                if(ans < 0) ans += mod;
                if(ans >= mod) ans -= mod;
            }
        }

        cout << ans << endl;
    }

    return 0;
}