27. AtCoder-Multiple Sequences
2022/7/15 23:23:33
本文主要是介绍27. AtCoder-Multiple Sequences,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接:Multiple Sequences
给定 \(n,m\),问存在多少长度为 \(n\) 的序列满足所有元素均 \(\in [1,m]\) 且对于序列中任意的相邻项,均满足后一项能被前一项整除。
结果对 \(998244353\) 取模。
一开始往dp的方向去想,发现没什么办法优化,说明还需要挖掘一些隐含的性质。容易注意到,序列中不同的数的个数并不多,是 \(\log m\) 级别的,尝试从这一点入手。
考虑一个简化版的问题,固定序列的最后一个元素为 \(m\),那么这样的序列的个数就相当于在前面添加 \(m\) 的所有质因子的方案数量。对于某个特定的质因数 \(p\),设 \(p^{\alpha}\parallel m\)(即 \(m\) 中最多包含 \(\alpha\) 个 \(p\)),这就相当于将 \(\alpha\) 个相同小球放到 \(n\) 个不同的盒子里,可以使用隔板法来解决。假设有 \(n-1\) 个隔板,算上球就是 \(n-1+\alpha\) 个位置,每个位置放一个隔板或者球,答案就是 \(\binom{n+\alpha -1}{n-1}\)。
在上一个问题中,针对一个单独的 \(m\) 而言,只需要计算不超过 \(\log m\) 次的组合数,显然这是可以接受的,所以这样枚举 \([1,m]\) 中的所有正整数即可。
现在我们得到了一个比较清晰的做法:先进行预处理,筛一遍质数,顺便得到每个数的最小质因数,再处理出阶乘及其逆元,然后枚举每个数作为序列最大值的方案数量计算贡献。代码如下:
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxn = 2e5 + 50; const ll mod = 998244353; namespace easymath { vector<int> prime; bool vis[maxn]; int minp[maxn]; void prime_sieve(int n) { fill(vis, vis + n + 1, 0); for (int i = 2; i <= n; ++i) { if (!vis[i]) { prime.push_back(i); minp[i] = i; } for (auto &&j : prime) { if (i * j > n) break; vis[i * j] = 1; minp[i * j] = j; if (i % j == 0) break; } } } ll ksm(ll b, ll k) { ll ret = 1; while (k) { if (k & 1) ret = ret * b % mod; b = b * b % mod; k /= 2; } return ret; } ll pinv(ll x) { return ksm(x, mod - 2); } ll fact[maxn], ifact[maxn]; void init_fact(int n) { fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % mod; ifact[n] = pinv(fact[n]); for (int i = n - 1; i >= 0; --i) ifact[i] = ifact[i + 1] * (i + 1) % mod; } ll C(int n, int m) { return fact[n] * ifact[n - m] % mod * ifact[m] % mod; } }; // namespace easymath using namespace easymath; void solve() { int m, n; cin >> n >> m; ll ans = 1; for (int i = 2; i <= m; ++i) { int now = i; ll tmp = 1; while (now > 1) { ll cnt = 0, p = minp[now]; while (now % p == 0) { now /= p; cnt++; } tmp = tmp * C(n + cnt - 1, cnt) % mod; } ans += tmp; } cout << ans % mod << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; prime_sieve(200000 + 10); init_fact(200000 + 30); while (T--) { solve(); } return 0; }
那么这种做法的复杂度究竟是多少呢?显然欧拉筛和预处理组合数的复杂度都是 \(\Theta(n)\),而统计答案时求组合数的次数是
\[\large \sum_{i=1}^{n}\Omega(i)=\sum_{i=1}^{n}\sum_{p^{\alpha}\parallel i}\alpha \]这个东西事实上是 \(n\log\log n\) 级别的,我也不会算,详细内容可以看 wiki。
这篇关于27. AtCoder-Multiple Sequences的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升