Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間7月前 (2025/04/24 06:01)推噓2(2推 0噓 0→)

2338. 知道要怎麼做之後自己刻出來還是好麻煩ㄛ== 我真的很崇拜chatgpt 還有gemini什麼的 # 先做質數表做階乘跟inverse 質因數分解抓去做牌組加起來這題步驟好多有點cf那味惹 using ll = long long; class Solution { public: int mod = 1e9 + 7; int idealArrays(int n, int mv) { vector<int> primes = gen_primes(mv); ll res = 0; res += mv; // base^0 = 1 int mx = log(mv) / log(2); mx = min(mx, n-1); // max put vector<ll> fact(n+15, 0), inv(n+15, 0); n--; // space // 'n' space, put at most 'mx' // C n pick 0 + C n pick 1 + ... + C n pick mx n += 15; // n + factor num fact[0] = 1; for(int i = 1; i <= n; i++){ fact[i] = fact[i-1] * i % mod; } inv[n] = power(fact[n], mod - 2); for(int i = n-1; i >= 0; i--){ inv[i] = inv[i+1] * (i+1) % mod; } n -= 15; // space n -= 1; // comma auto&& factorize = [&](int time){ ll res = 1; int cnt = 0; for(int p: primes){ cnt = 0; while(time > 0 and time % p == 0){ cnt++; time /= p; } if(cnt) res = res * fact[cnt + n] % mod * inv[cnt] % mod * inv[n] % mod; if(p * p > time) break; } if(time > 1) res = res * (n + 1) % mod ; return res; }; for(int time = 2; time <= mv; time++){ res += factorize(time) * (int)(mv / time); res %= mod; } return res; } ll power(ll a, ll b){ ll res = 1; while(b) { if(b % 2) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } vector<int> gen_primes(int mx){ vector<bool> is_prime(mx + 1, true); vector<int> primes; is_prime[0] = false; is_prime[1] = false; for(int i = 2; i <= mx; i++){ if(is_prime[i]){ primes.emplace_back(i); for(int j = i*2; j <= mx; j += i){ is_prime[j] = false; } } } return primes; } }; ※ 引述《sixB (6B)》之銘言： : 2338. : 牌組真的好難 : 我快吐了 : 很認真看懂mod inv lc介面改這什麼ㄐㄅ手機在problem拉半天找不到daily -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg