當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

E. Mocha and Stars（莫比乌斯反演、简单dp）

發布時間：2023/12/4 编程问答 29 豆豆

生活随笔收集整理的這篇文章主要介紹了 E. Mocha and Stars（莫比乌斯反演、简单dp）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

E. Mocha and Stars

$∑a1=l1r1∑a2=l2r2?∑an=lnrn[a1+a2+?+an≤m][gcd?(a1,a2,…,an)=1]\sum_{a_1 = l_1} ^{r_1} \sum_{a_2 = l_2} ^{r_2} \dots \sum_{a_n = l_n} ^{r_n} [a_1 + a_2 + \dots + a_n \le m][\gcd(a_1, a_2, \dots, a_n) = 1]\\$
有 $\le n \le 50, 1 \le m \le 10 ^ 5, 1 \le l_i \le r_i \le m$ ，對上述答案對 $998244353998\ 244\ 353$ 取模。

$∑a1=l1r1∑a2=l2r2?∑an=lnrn[a1+a2+?+an≤m][gcd?(a1,a2,…,an)=1]∑k=1mμ(k)∑a1=?l1k??r1k?∑a2=?l2k??r2k??∑an=?lnk??rnk?[a1+a2+?+an≤?md?]\sum_{a_1 = l_1} ^{r_1} \sum_{a_2 = l_2} ^{r_2} \dots \sum_{a_n = l_n} ^{r_n} [a_1 + a_2 + \dots + a_n \le m][\gcd(a_1, a_2, \dots, a_n) = 1]\\ \sum_{k = 1} ^{m} \mu(k) \sum_{a_1 = \lceil \frac{l_1}{k} \rceil} ^{\lfloor \frac{r_1}{k} \rfloor} \sum_{a_2 = \lceil \frac{l_2}{k} \rceil} ^{\lfloor \frac{r_2}{k} \rfloor} \dots \sum_{a_n = \lceil \frac{l_n}{k} \rceil} ^{\lfloor \frac{r_n}{k} \rfloor} [a_1 + a_2 + \dots + a_n \le \lfloor \frac{m}ze8trgl8bvbq \rfloor]\\$

其中 $∑a1=?l1k??r1k?∑a2=?l2k??r2k??∑an=?lnk??rnk?[a1+a2+?+an≤?md?]\sum\limits_{a_1 = \lceil \frac{l_1}{k} \rceil} ^{\lfloor \frac{r_1}{k} \rfloor} \sum\limits_{a_2 = \lceil \frac{l_2}{k} \rceil} ^{\lfloor \frac{r_2}{k} \rfloor} \dots \sum\limits_{a_n = \lceil \frac{l_n}{k} \rceil} ^{\lfloor \frac{r_n}{k} \rfloor} [a_1 + a_2 + \dots + a_n \le \lfloor \frac{m}ze8trgl8bvbq \rfloor]$ ，可以考慮 $d p$ 求解， $f [i] [j]$ ，表示前 $i$ 個數，和為 $j$ 的方案有多少，復雜度 $\times \lfloor \frac{m}ze8trgl8bvbq \rfloor$ 。

由此，整體復雜度是 $\times m \times \log m$ 。

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10, mod = 998244353;int mu[N], prime[N], L[N], R[N], f[N], pre[N], n, cnt, M;bool st[N];inline int add(int x, int y) {return x + y < mod ? x + y : x + y - mod; }inline int sub(int x, int y) {return x >= y ? x - y : x - y + mod; }void init() {mu[1] = 1;for (int i = 2; i < N; i++) {if (!st[i]) {prime[++cnt] = i;mu[i] = -1;}for (int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {st[i * prime[j]] = 1;if (i % prime[j] == 0) {break;}mu[i * prime[j]] = -mu[i];}} }int F(int d) {int m = M / d, sum = 0;for (int i = 1; i <= n; i++) {int l = (L[i] + d - 1) / d, r = R[i] / d;if (l > r) {return 0;}sum += l;}if (sum > m) {return 0;}for (int i = 1; i <= m; i++) {f[i] = 0;}for (int i = 1; i <= n; i++) {int l = (L[i] + d - 1) / d, r = R[i] / d;if (i == 1) {for (int j = l; j <= r; j++) {f[j] = 1;}continue;}for (int j = 1; j <= m; j++) {pre[j] = add(pre[j - 1], f[j]);f[j] = 0;}for (int j = 1; j <= m; j++) {// x + {l, l + 1, ………, r} = j, x = [j - r, j - l]int L = max(1, j - r), R = j - l;if (L > R) {continue;}f[j] = sub(pre[R], pre[L - 1]);}}int ans = 0;for (int i = 1; i <= m; i++) {ans = add(ans, f[i]);}return ans; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);init();scanf("%d %d", &n, &M);for (int i = 1; i <= n; i++) {scanf("%d %d", &L[i], &R[i]);}int ans = 0;for (int i = 1; i <= M; i++) {if (mu[i] == -1) {ans = sub(ans, F(i));}else if (mu[i] == 1) {ans = add(ans, F(i));}}printf("%d\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的E. Mocha and Stars（莫比乌斯反演、简单dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：【数学与算法】贝塞尔(Bézier)曲线
下一篇： linux chattr命令