Combinatorics | No DP | O(n) time | 0 ms in Rust
Approach\n\nLet\'s understand the problem:\n\nGiven an array nums, we have to count how many ways we can split nums into a and b such that:\n\n1. $a_i + b_i = n
# Approach\n\nLet\'s understand the problem:\n\nGiven an array `nums`, we have to count how many ways we can split `nums` into `a` and `b` such that:\n\n1. $a_i + b_i = nums_i$\n2. $a_{i-1} \\le a_i$\n3. $b_{i-1} \\ge b_i$\n\nFrom $(1)$ and $(3)$ we get\n$\n\\begin{aligned}\n&nums[i-1]-a_{i-1} \\ge nums[i]-a_i \\\\\n\\implies &a_i \\ge a_{i-1} + (nums[i] - nums[i-1])\n\\end{aligned}\n$\nIncluding $(2)$, we get $a_i \\ge a_{i-1} + \\max(0, nums[i] - nums[i-1])$\n\nExpanding the recurrence for an array of 4 elements, we get\n\n$\n\\begin{aligned}\n0 &\\le a_0 \\\\\na_0 + \\delta_0 &\\le a_1 \\\\\na_1 + \\delta_1 &\\le a_2 \\\\\na_2 + \\delta_2 &\\le a_3 \\\\\na_3 &\\le nums[3]\n\\end{aligned}\n$ where $\\delta_i = \\max(0, nums[i+1] - nums[i])$\n\nAdding the above inequalities, we get\n\n$\n\\begin{aligned}\n\\delta_0 + \\delta_1 + \\delta_2 &\\le \\\\\n\\delta_0 + \\delta_1 + \\delta_2 + a_0 &\\le \\\\\n\\delta_1 + \\delta_2 + a_1 &\\le \\\\\n\\delta_2 + a_2 &\\le \\\\\na_3 &\\le nums[3]\n\\end{aligned}\n$\n\nUsing $t_i$ to represent $a_i + \\sum_{i \\le k \\lt n-1}{\\delta_k}$ and $R$ for $nums[n-1]$ we get the following relation\n\n$\n\\begin{aligned}\n\\sum{\\delta_k} &\\le t_0 \\le t_1 \\le t_2 \\le t_3 \\le R\n\\end{aligned}\n$\n\nNow, we have to compute the number of different ways to choose $t_i$ from the closed range of integers $[L, R]$ where $L$ represents $\\sum{\\delta_k}$\n\nNow we have to count the different ways of assigning $\\lt$ or $=$ between $t_{i-1}$ and $t_i$\n\n1. $L \\le t_0 \\lt t_1 \\lt t_2 \\lt t_3 \\le R$.\nThis choice can be computed in $\\binom{R-L+1}{4}$\n2. $L \\le t_0 = t_1 \\lt t_2 \\lt t_3 \\le R$ - with one equal operator, there can be $3$ ways to define the relation with one $=$ and two $\\lt$ operator $\\implies \\binom{3}{1} * \\binom{R-L+1}{3}$\n3. $L \\le t_0 = t_1 = t_2 \\lt t_3 \\le R$ - with two equal operators, we get $\\binom{3}{2} * \\binom{R-L+1}{2}$\n4. $L \\le t_0 = t_1 = t_2 = t_3 \\le R$ - all integers are equal, can be chosen in $\\binom{3}{3} * \\binom{R-L+1}{1}$\n\nGeneralizing for array of $n$ elements, we have\n\n$\\boxed{\\textit{number of ways} = \\sum_{0 \\le k \\le n-1}{\\binom{n-1}{k} * \\binom{R-L+1}{n-k}}}$\n\nUsing [Vandermonde\'s Identity](https://en.wikipedia.org/wiki/Vandermonde%27s_identity), we get\n\n$\\boxed{\\textit{number of ways} = \\binom{R-L+1 + n-1}{n} = \\binom{R-L+n}{n}}$\n\n# Complexity\n- Time complexity: $O(n)$\n- Space complexity: $O(1)$\n\n\n# Code\n```rust []\n// \u0939\u0930 \u0939\u0930 \u092E\u0939\u093E\u0926\u0947\u0935\n\nfn gcd(a: i64, b: i64) -> (i64, i64, i64) {\n    let mut s = (1, 0);\n    let mut t = (0, 1);\n    let mut r = (a, b);\n    while r.1 != 0 {\n        let q = r.0/r.1;\n        s = (s.1, s.0 - q*s.1);\n        t = (t.1, t.0-q*t.1);\n        r = (r.1, r.0 - q*r.1);\n    }\n    (s.0, t.0, r.0)\n}\n\n#[inline]\nfn inverse<const MOD: i64>(n: i64) -> i64 {\n    let mut v = gcd(n, MOD).0;\n    if v < 0 {\n        v += MOD;\n    }\n    v\n}\n\nimpl Solution {\n    pub fn count_of_pairs(nums: Vec<i32>) -> i32 {\n        let len = nums.len() as i64;\n        let l: i64 = nums.windows(2).map(|w| (w[1] as i64 - w[0] as i64).max(0))\n            .sum();\n        let r = *nums.last().unwrap() as i64;\n        if l > r {\n            return 0;\n        }\n        const MOD: i64 = 1_000_000_007;\n        let size = r-l+1;\n        let num = (size..=size+len-1).fold(1, |p, e| (p*e)%MOD);\n        let den = (1..=len).fold(1, |p, e| (p*e) % MOD);\n        (num * inverse::<MOD>(den) % MOD) as i32\n    }\n}\n```\n```c []\n// \u0939\u0930 \u0939\u0930 \u092E\u0939\u093E\u0926\u0947\u0935\n#include <stdint.h>\n\ntypedef int64_t i64;\ntypedef uint64_t u64;\n\n#define MOD 1000000007L\n\ni64 gcd(i64 a, i64 b, i64 *x, i64 *y) {\n    i64 q, tmp;\n    i64 s[] = {1, 0};\n    i64 t[] = {0, 1};\n    i64 r[] = {a, b};\n\n    while (r[1]) {\n        q = r[0] / r[1];\n        tmp = s[0] - q*s[1];\n        s[0] = s[1];\n        s[1] = tmp;\n        tmp = t[0] - q*t[1];\n        t[0] = t[1];\n        t[1] = tmp;\n        tmp = r[0] - q*r[1];\n        r[0] = r[1];\n        r[1] = tmp;\n    }\n\n    *x = s[0];\n    *y = t[0];\n    return r[0];\n}\n\ni64 inverse(i64 n, i64 mod) {\n    i64 x, y;\n    gcd(n, mod, &x, &y);\n    if (x < 0) {\n        x += mod;\n    }\n    return x;\n}\n\nint countOfPairs(int* nums, int len) {\n    i64 l = 0;\n    for (i64 i = 1; i != len; i++) {\n        if (nums[i] > nums[i-1]) {\n            l += nums[i] - nums[i-1];\n        }\n    }\n    i64 r = nums[len-1];\n    if (r < l) {\n        return 0;\n    }\n    i64 numer = 1;\n    i64 denom = 1;\n    for (i64 i = 0; i != len; i++) {\n        numer = numer * (r-l + len - i) % MOD;\n        denom = denom * (i+1) % MOD;\n    }\n    return (int)(numer * inverse(denom, MOD) % MOD);\n}\n```
['Math', 'C', 'Combinatorics', 'Rust']