Educational Codeforces Round 88 (Rated for Div. 2) E（数学）

Educational Codeforces Round 88 (Rated for Div. 2)E

题目大意: 给你n，k(1<=k<=n<=5e5)，从1到n中选k个数组成一个严格递增序列，如果对任何正整数，依次模上这k个数，无论这k个数如何排列得到的答案都相同，那么称这个序列为好序列，求好序列的个数%998244353

思路： 最后的余数是和最小的那个数的位置有关的，通过打表发现其余数是最小数的倍数时，无论位置，最后的余数都相同。
所以我们利用组合数，枚举最小的数i，然后从剩下的(n/i)-1个能整除i的数中随意挑k-1个即可。
证明：
设ai是最小的数，当ai出现后，后面的数字必定大于余数，使用后面的余数不变。
ai前面的数，x=（nai）+m，则余数为n，当前面的数是ai的k倍数时，x=（n1kai）+n2ai+m.其中（n1kai）+n2ai=（nai）。所有最后的余数还是等于m，无论他们的位置如何。
代码：

#include <bits/stdc++.h> using ll = long long; using namespace std; const int mod = 998244353;ll fpow(ll a, ll b) {ll res = 1;while (b > 0) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res; }ll inv(ll x) {return fpow(x, mod - 2); }ll C(ll n, ll m) {if (n < m) return 0;ll res = 1;ll mi = min(m, n - m);for (int i = 1; i <= mi; i++)res = res * (n - i + 1) % mod * inv(i) % mod;return res; }int main() {int n, k; cin >> n >> k;ll ans = 0;for (int i = 1; i <= n; i++)ans += C(n / i - 1, k - 1), ans %= mod;cout << ans << "\n"; }

总结

以上是生活随笔为你收集整理的Educational Codeforces Round 88 (Rated for Div. 2) E（数学）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。