Power_Inverse.code-snippets

{
	"Power_Inverse": {
		"prefix": "Power_Inverse",
		"body": [
		  "template < typename T = int > struct Power_Inverse {",
		  "    ",
		  "    T n, r, mod;",
		  "    vector < T > fact, inv;",
		  "",
		  "    T fast_power(T b, T e, T MOD){",
		  "        T power = 1;",
		  "        while(e){",
		  "            if(e & 1) power = mod_combine(power, b, MOD);",
		  "            e >>= 1, b = mod_combine(b, b, MOD);",
		  "        }",
		  "        return power % MOD;",
		  "    }",
		  "",
		  "    T Inverse(T N, T MOD){",
		  "        return fast_power(N, MOD - 2, MOD) % MOD;",
		  "    }",
		  "",
		  "    Power_Inverse(T N, T R, T MOD){",
		  "        n = N, r = R, mod = MOD;",
		  "        fact.assign(n + 10, 1), inv.resize(n + 10, 1);",
		  "        for(ll i = 1; i <= n; i++){",
		  "            fact[i] = mod_combine(fact[i - 1], i, mod);",
		  "            inv[i] = Inverse(fact[i], mod);",
		  "        }",
		  "    }",
		  "",
		  "    // Combination",
		  "",
		  "    T nCr(){",
		  "        if(r > n) return 0ll;",
		  "        return (((fact[n] % mod) * (inv[r] % mod) % mod) * (inv[n - r] % mod)) % mod;",
		  "    }",
		  "",
		  "    // Permutation",
		  "",
		  "    T nPr(){",
		  "        if(r > n) return 0ll;",
		  "        return ((fact[n] % mod) * (inv[r] % mod)) % mod;",
		  "    }",
		  "",
		  "};"
		],
		"description": "Power_Inverse"
	}
}