[C++, Java, Python] Inclusion Exclusion | Math | O(logn)
Intuition\nHappy Diwali!!\nI\'ll be sharing my though process during contest.\n\nAs we can see that we need atleast 1 L, 1 T and 2 E somewhere in our string. Th
# Intuition\nHappy Diwali!!\nI\'ll be sharing my though process during contest.\n\nAs we can see that we need atleast 1 L, 1 T and 2 E somewhere in our string. They need not be present in order as it can be rearranged afterwards. Hence, out of $n$ letters, $4$ are fixed and for the rest of $n-4$ letters we have to make permutations and combinations.\n\nOut of those $n-4$ letters, suppose we take\n```\na = x1 times\nb = x2 times\n.\n.\nz = x26 times\n\nConstraint that x1 + x2 + ... + x26 = n - 4\n0 <= x1, x2, ..., x26 <= n - 4\n```\n\nTherefore, in total we have\n```\na = x1 times\nb = x2 times\n.\n.\ne = x5 + 2 times\n.\n.\nl = x12 + 1 times\n.\n.\nt = x20 + 1 times\n.\n.\nz = x26 times\n```\n\nNumber of ways to arrange these letters on $n$ indices is given by:\n\n$$\\displaystyle\\frac{n!}{x_{1}!x_{2}!...(x_{5}+2)!...(x_{12}+1)!...(x_{20}+1)!...x_{26}!}$$\n\nAnd, ofcourse we can precompute factorials, mod inverse factorials. But the problem is we have to try all possible combinations of variables $(x_1,x_2,...,x_{26})$.\n\nIt is not feasible to do it the forward way. Hence, start thinking backwards.\nWhat are the total number of strings regardless good or bad? Since, every index has $26$ choices, it is $26^n$.\nWhat if we somehow calculate number of bad strings and subtract the answer from it to get good strings?\n\nWhat makes a string bad?\n```\nC1 = 0 L (no L present in whole string)\nC2 = 0 T (no T present in whole string)\nC3 = 0 E (no E present in whole string)\nC4 = 1 E (only 1 E present in whole string)\n```\n\nThese 4 cases $(C_1, C_2, C_3, C_4)$ make a string bad, or a combination of them.\nThis gives the intuition of Inclusion Exclusion Principle.\n\nCount of bad strings can be written as\n\n$$singletons - pairs + triplets - quadruples$$\n\n$$= \\bigcup_{i} |C_i| - \\bigcup_{i,j} |C_i \\cap C_j| + \\bigcup_{i,j,k} |C_i \\cap C_j \\cap C_k| - \\bigcup_{i,j,k,l} |C_i \\cap C_j \\cap C_k \\cap C_l|\n$$\n\nExpanding, it can be written as\n$$+(|C_1| + |C_2| + |C_3| + |C_4|)$$\n\n$$-(|C_1 \\cap C_2| + |C_1 \\cap C_3| + |C_1 \\cap C_4| + |C_2 \\cap C_3| + |C_2 \\cap C_4| + |C_3 \\cap C_4|)$$\n\n$$+(|C_1 \\cap C_2 \\cap C_3| + |C_1 \\cap C_2 \\cap C_4| + |C_1 \\cap C_3 \\cap C_4| + |C_2 \\cap C_3 \\cap C_4|)$$\n\n$$-(|C_1 \\cap C_2 \\cap C_3 \\cap C_4|)$$\n\n\nNow,\n1. $C_3 \\cap C_4 = \\phi$ (a string can\'t have 0 E and 1 E simultaneously)\n2. $|C_1|$ can be calculated as the number of ways to form string with 0 L. Means we have $25$ choices for all $n$ letters. $|C_1|=25^n$.\n3. $|C_4|$ can be calculated as the number of ways to form string with 1 E. First select $1$ position out of $n$ indices on which E should be placed (${}^nC_1$ choices). Then for remaining $n-1$ letters we have $25^{n-1}$ choices. $|C_4| = {}^nC_1.25^{n-1}$.\n\nSimilarly, calculate other values.\n\nNumber of bad strings will be\n$$+(25^n + 25^n + 25^n + {}^nC_1.25^{n-1})$$\n\n$$-(24^n + 24^n + {}^nC_1.24^{n-1} + 24^n + {}^nC_1.24^{n-1} + 0)$$\n\n$$+(23^n + {}^nC_1.23^{n-1} + 0 + 0)$$\n\n$$-(0)$$\n\n$$\n=(n+75).25^{n-1} - (2n+72).24^{n-1} + (n+23).23^{n-1}\n$$\n\nNumber of good strings will be\n$$\n26^n - (n+75).25^{n-1} + (2n+72).24^{n-1} - (n+23).23^{n-1}\n$$\n\n# Approach\n\n**Modulo Arithmetic and Binary Exponentiation**\nWe need a function to calculate power with modulo. Library functions can\'t be used (in most of the langugages) because powers can be much larger than the numbers stored in $int$ data type. We need to handle overflow while calculating power using the fact:\n\n$$(a * b) \\mod m = ((a \\mod m) * (b \\mod m)) \\mod m$$\n\nAnd power can be calculated as\n$$\nx^n \\mod m = ((x \\mod m) * (x \\mod m) * ... n \\enspace times ... * (x \\mod m)) \\mod m\n$$\n$$\nx^n \\mod m = ((x^{n-1} \\mod m) * (x \\mod m)) \\mod m\n$$\n```\npow(x, n, mod)\n    result = 1\n    for i = 1 to n:\n        result = (result * x) % mod\n    return result\n```\n\nTime complexity of this approach would be $O(n)$. But, there is another method to calculate powers using binary exponentiation with time $O(\\log n)$.\n\nTaking an example, calculate $2^{11} \\mod 1000$:\n- Convert exponent in binary form $(11)_{10}=(1011)_2$.\n- Result can be written as\n  $2^{1011}=2^{2^3 + 2^1 + 2^0}=2^{2^3}.2^{2^1}.2^{2^0}$\n- In below program, we maintain variable $p$ having value of $2^{2^b} \\mod m$.\n- $2^{2^{b+1}} \\mod m$ can be calculated by squaring $p$.\n  $2^{2^{b+1}} \\mod m = (2^{2^b} \\mod m)^2 \\mod m$\n- Traversing on the exponent bit by bit, whenever the Least Signifacnt Bit is $1$, we multiply this value of $p$ to the $result$.\n\n# Code\n```C++ []\nclass Solution {\nprivate:\n    long pow(long x, long n, long mod) {\n        long result = 1, p = x % mod;\n        while (n) {\n            if (n & 1) {\n                result = (result * p) % mod;\n            }\n            p = (p * p) % mod;\n            n >>= 1;\n        }\n        return result;\n    }\n    \npublic:\n    int stringCount(int n) {\n        long mod = 1e9 + 7;\n        return ((\n            + pow(26, n, mod)\n            - (n + 75) * pow(25, n - 1, mod)\n            + (2 * n + 72) * pow(24, n - 1, mod)\n            - (n + 23) * pow(23, n - 1, mod)\n        ) % mod + mod) % mod;\n    }\n};\n```\n```Java []\nclass Solution {\n    private long pow(long x, long n, long mod) {\n        long result = 1, p = x % mod;\n        while (n != 0) {\n            if ((n & 1) != 0) {\n                result = (result * p) % mod;\n            }\n            p = (p * p) % mod;\n            n >>= 1;\n        }\n        return result;\n    }\n\n    public int stringCount(int n) {\n        long mod = (int)1e9 + 7;\n        return (int)(((\n            + pow(26, n, mod)\n            - (n + 75) * pow(25, n - 1, mod)\n            + (2 * n + 72) * pow(24, n - 1, mod)\n            - (n + 23) * pow(23, n - 1, mod)\n        ) % mod + mod) % mod);\n    }\n}\n```\n```Python []\nclass Solution:\n    def stringCount(self, n: int) -> int:\n        mod = 10 ** 9 + 7\n        return (\n            + pow(26, n, mod)\n            - (n + 75) * pow(25, n - 1, mod)\n            + (2 * n + 72) * pow(24, n - 1, mod)\n            - (n + 23) * pow(23, n - 1, mod)\n        ) % mod\n```\n\n# Complexity\n- Time complexity: $O(\\log n)$\n- Space complexity: $O(1)$\n\n---\n\n> Another way to think from the factorial formula.\n\nNumber of ways to arrange these letters on $n$ indices is given by:\n\n$$\\displaystyle\\frac{n!}{x_{1}!x_{2}!...(x_{5}+2)!...(x_{12}+1)!...(x_{20}+1)!...x_{26}!}$$\n\nIterating over all possible values of $(x_1,x_2,...x_{26})$ where each one of them will have a loop for $0$ to $n-4$. That\'s 26 nested loops (or 25 if you use $x_{26} =n-4-(x_1+x_2+...+x_{25})$) having times complexity $n^{26}$.\n\nMathematically it will work too and give correct answer.\n\nThis summation of all terms can be reduced to single formula using multinomial theorem.\nThe factorial term is just the coefficient of term $a^{x_1}...z^{x_{26}}$ in the expansion of $(a+b+...z)^n$. Sum of all these coefficients can be calculated by putting $a=b=...=z=1$ which comes out to be $26^n$.\n\nBut if we want sum of good coefficients only, then either we calculate them using loops or we calculate it by first calculating bad coefficients. Now this will be dependent on question, which one will be easier to calculate.
['Math', 'C++', 'Java', 'Python3']