2338. Count the Number of Ideal Arrays
You are given two integers n and maxValue, which are used to describe an ideal array.
A 0-indexed integer array arr of length n is considered ideal if the following conditions hold:
- Every arr[i] is a value from 1 to maxValue, for 0 <= i < n.
- Every arr[i] is divisible by arr[i - 1], for 0 < i < n.
Return the number of distinct ideal arrays of length n. Since the answer may be very large, return it modulo 109 + 7.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| class Solution { long long fact[10101] = {}, inv[10101] = {}; long long mod = 1e9 + 7; long long modpow(long long n, long long x) { if(!x) return 1; long long res = modpow(n,x>>1); res = (res * res) % mod; if(x & 1) res = (res * n) % mod; return res; } long long nCr(long long x, long long y) { if(x < y) return 0; return fact[x] * inv[x-y] % mod * inv[y] % mod; } long long helper(vector<int>& A, int& n, int& ma) { long long gap = A.back(); long long res = nCr(n, A.size() - 1); for(long long i = gap * 2; i <= ma; i += gap) { A.push_back(i); res = (res + helper(A,n,ma)) % mod; A.pop_back(); } return res; } public: int idealArrays(int n, int ma) { fact[0] = inv[0] = 1; for(int i = 1; i <= n + 1; i++) { fact[i] = (fact[i-1] * i) % mod; inv[i] = modpow(fact[i], mod-2); } return helper(vector<int>() = {1}, n, ma); } };
|