51Nod 1269. Dev and Flowers[不定方程](容斥原理/母函数)

日付: 10月 31, 2018

## Problem
求多元一次不定方程(Linear Diophantine Equation)解的数量 $$x_1+x_2+\cdots+x_n=m, \quad 0 \le x_i \le s_i$$

数据范围：$1\le n \le 20, \ 1\le s_i \le 10^{16}, \ 1\le m \le 10^{18}$

## Solution
如果限制条件只有$0\le x_i$就是经典的“多元一次不定方程非负整数解个数”问题，可以转化成$x_1+x_2+\cdots+x_n=m+n$的正整数解个数问题，然后用隔板法解，答案是$\binom{m+n-1}{n-1}$。

因为$n$很小，可以用容斥原理(Inclusion-Exclusion Principle)来做。我们需要从非负整数解中排除满足条件$x_i > s_i$的部分。如果某个$x_i>s_i$成立，问题可以转化为求$x_1+x_2+\cdots+x_n=m-(s_i+1)$的非负整数解个数。

枚举一个bitmask表示需要排除那几个条件，算出这种情况的数量后，根据排除条件数量的奇偶性从答案中加减即可。复杂度$O(n\cdot2^n)$

本题以及类似有限制不定方程解数量的问题还有一较为通用的解法，即母函数(Generating Function)。
主要根据两个公式$$\sum_{n=0}^{\infty}x^n = \frac{1}{1-x}$$ $$\sum_{n=0}^{\infty}\binom{n+k}{k}x^n = \frac{1}{(1-x)^{k+1}}$$
比如本题可以构造式子$A=\prod_{i=1}^n\sum_{j=0}^{s_i}x^j$，$A$的$x^m$项系数就是答案

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

struct Combine {
    using LL = long long;
    static int inv(LL x, int m) {
        return x > m ? inv(x % m, m) : x > 1 ? inv(m % x, m) * (m - m / x) % m : x;
    }
    static int comod(LL n, LL k, int m = 1e9 + 7) {
        if (k + k > n) return comod(n, n - k, m);
        int num = 1, den = 1;
        for (int i = 1; i <= k; i++) num = num * ((n - i + 1) % m) % m, den = 1LL * den * i % m;
        return 1LL * num * inv(den, m) % m;
    }
    static int lucas(LL n, LL k, int m = 10007) {
        assert(m < 1e5);
        return n || k ? 1LL * lucas(n / m, k / m, m) * comod(n % m, k % m, m) % m : 1;
    }
    int m;
    vector<LL> F;
    Combine(int n, int m) : m(m), F(n, 1) { for (int i = 1; i < n; i++) F[i] = F[i - 1] * i % m; }
    int com(LL n, LL k) { return F.at(n) * inv(F.at(n - k) * F[k], m) % m; }
    int per(LL n, LL k) { return F.at(n) * inv(F.at(k), m) % m; }
};

// 51Nod. 1269
int main() {
    using LL = long long;
    const int Mod = 1e9 + 7;
    int n;
    scanf("%d", &n);
    LL k, ans = 0;
    scanf("%lld", &k);
    vector<LL> S(n);
    for (int i = 0; i < n; i++) scanf("%lld", &S[i]);
    for (int s = 0; s < (1 << n); s++) {
        bool flag = __builtin_popcount(s) & 1;
        LL t = k;
        for (int i = 0; i < n; i++) if (1 << i & s) t -= S[i] + 1;
        if (t < 0) continue;
        ans += (flag ? -1 : 1) * Combine::comod(t + n - 1, n - 1, Mod);
        ans = (ans + Mod) % Mod;
    }
    printf("%lld\n", ans);
    return 0;
}
```

KONGROOの基地

このブログを検索

51Nod 1269. Dev and Flowers[不定方程](容斥原理/母函数)

コメント

コメントを投稿