差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:alchemist:weekly_digest_1 [2020/05/08 20:08]
hardict [龙鹏宇 Hardict]
+++ 2020-2021:teams:alchemist:weekly_digest_1 [2020/05/12 01:11] (当前版本)
mountvoom [肖思炀 MountVoom]
@@ 行 21: / 行 21: @@
 模板题：https:%%//%%ac.nowcoder.com/acm/contest/5157/D
-很容易从题目的形式看出来实际上就是对四个数列求三重卷积，第一重是$i|j$的子集卷积，第二重$(i|j)+k$的FFT/NTT，第三重是$((i|j)+k)\otimes h$的FWT的异或卷积。代码如下：
+很容易从题目的形式看出来实际上就是对四个数列求三重卷积，第一重是$i|j$的子集卷积，第二重$(i|j)+k$的FFT/NTT，第三重是$((i|j)+k)\otimes h$的FWT的异或卷积。代码参考个人主页的子集卷积内容。
-<code cpp>
+===== 龙鹏宇 Hardict =====
-#include <bits/stdc++.h>
-#define N 262144
+==== 总结 ====
-using namespace std;
+  - 多组数据多组询问尽可能考虑预处理,在单个数容斥中一般$\mu(i) \neq 0$才有贡献,可以预处理进行优化
+  - 计算几何处理相同点可以$\pm epsilon$
+==== 统计数列中上升子序列个数====
-const int mod = 998244353, inv2 = 499122177;
+对应数列$\{a_{i}\}_{i=1}^{n}$
-int n;
+考虑一个dp转移:$f[n]=1+\sum_{1\leq i <n,a[i] < a[n]}f[i]$
-int rev[N], lim, hib;
-int A[N], B[N], C[N], D[N], popc[N];
-int f[20][N], g[20][N], h[20][N];
-inline int Add(int u, int v) { return (u += v) >= mod ? u - mod : u; }
+可以利用数组数组解决,可是一般数列中会出现相同数,需要预先离散化
-inline void Inc(int &u, int v) { if ((u += v) >= mod) u -= mod; }
+这里有一个技巧,假设数列长度为$n$,可以令$b[i]=(n+1)*a[i]+n-i$排序后利用$b[]$离散化即可得到严格上升下对应的$rank$
-inline int fpm(int x, int y) {
+若令$b[i]=(n+1)*a[i]+i$则可得到不严格上升的$rank$
-    int r = 1;
-    while (y) {
-        if (y & 1) r = 1LL * x * r % mod;
-        x = 1LL * x * x % mod, y >>= 1;
-    }
-    return r;
-}
-inline int read() {
+=== 例题 ===
-    int x = 0;
+[[http://codeforces.com/gym/101192/problem/A|2015-2016 6th BSUIR Open Programming Contest. Semifinal A题]]
-    char ch = getchar();
-    while (!isdigit(ch)) ch = getchar();
-    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
-    return x;
-}
-void getrev(int len) {
+**题意:**
-    lim = 1, hib = -1;
-    while (lim < len) lim <<= 1, ++hib;
-    for (int i = 0; i < lim; ++i)
-        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << hib);
-}
-void fwtOr(int *a, bool type) {
+给定数列$\{a_{i}\}_{i=1}^{n},\{b_{i}\}_{i=1}^{n},a_{i} \leq 10^{9},b_{i} \leq 10^{6}$,求所有$\{a_{i}\}_{i=1}^{n}$上升子序列的下标对应的$\{b_{i}\}_{i=1}^{n}$的子序列gcd的和
-    for (int mid = 1; mid < lim; mid <<= 1)
-        for (int i = 0; i < lim; i += (mid << 1))
-            for (int j = 0; j < mid; ++j)
-                if (type) Inc(a[i + mid + j], a[i + j]);
-                else Inc(a[i + mid + j], mod - a[i + j]);
-}
-void fwtXor(int *a, bool type) {
+**题解:**
-    static int x, y;
-    for (int mid = 1; mid < n; mid <<= 1)
-        for (int len = mid << 1, i = 0; i < n; i += len)
-            for (int j = 0; j < mid; ++j) {
-                x = a[i + j], y = a[i + mid + j];
-                a[i + j] = Add(x, y), a[i + mid + j] = Add(x, mod - y);
-                if (!type)
-                    a[i + j] = 1LL * inv2 * a[i + j] % mod,
-                            a[i + mid + j] = 1LL * inv2 * a[i + mid + j] % mod;
-            }
-}
-void NTT(int *a, bool type) {
+考虑满足新数列$\{p\}=\{a_{i} : d |b_{i}\}$,求解$\{p\}$的上升子序列个数$cnt_{d}$再乘上容斥系数$coef_{d}$
-    for (int i = 0; i < lim; ++i)
-        if (i < rev[i])
-            swap(a[i], a[rev[i]]);
-    static int x, y;
-    for (int mid = 1; mid < lim; mid <<= 1) {
-        int len = mid << 1, wn = fpm(3, (mod - 1) / len);
-        for (int i = 0; i < lim; i += len)
-            for (int j = 0, w = 1; j < mid; ++j, w = 1LL * w * wn % mod) {
-                x = a[i + j], y = 1LL * w * a[i + mid + j] % mod;
-                a[i + j] = Add(x, y), a[i + mid + j] = Add(x, mod - y);
-            }
-    }
-    if (!type) {
-        reverse(a + 1, a + lim);
-        int inv = fpm(lim, mod - 2);
-        for (int i = 0; i < lim; ++i)
-            a[i] = 1LL * inv * a[i] % mod;
-    }
-}
-int main() {
+即可得到$ans=\sum_{d=1}^{maxb}cnt_{d}coef_{d},maxb=\max\limits_{1 \leq i\leq n}\{b_{i}\}$
-    n = read(), ++n;
-    getrev(n + n - 1);
-    for (int i = 0; i < lim; ++i) popc[i] = popc[i >> 1] + (i & 1);
-    for (int i = 0; i < n; ++i) A[i] = read(), f[popc[i]][i] = A[i];
-    for (int i = 0; i < n; ++i) B[i] = read(), g[popc[i]][i] = B[i];
-    for (int i = 0; i < n; ++i) C[i] = read();
-    for (int i = 0; i < n; ++i) D[i] = read();
-    for (int i = 0; i <= 17; ++i)
+而对于容斥系数,考虑容斥过程
-        fwtOr(f[i], true), fwtOr(g[i], true);
-    for (int sa = 0; sa <= 17; ++sa)
-        for (int sb = 0; sb + sa <= 17; ++sb)
-            for (int i = 0; i < lim; ++i)
-                h[sa + sb][i] = (h[sa + sb][i] + 1LL * f[sa][i] * g[sb][i]) % mod;
-    for (int i = 0; i <= 17; ++i)
-        fwtOr(h[i], false);
-    for (int i = 0; i < lim; ++i)
-        A[i] = h[popc[i]][i];
-    NTT(A, true), NTT(C, true);
+分析每一个$d$的实际贡献,其在$e|d$时都会被统计,对d单独进行容斥$coef_{d}=\sum_{e|d}e\mu(\frac{d}{e})$
-    for (int i = 0; i < lim; ++i)
-        A[i] = 1LL * A[i] * C[i] % mod;
-    NTT(A, false);
-    fwtXor(A, true), fwtXor(D, true);
+这里可以预处理所有非$\mu$进行预处理
-    for (int i = 0; i < lim; ++i)
-        A[i] = 1LL * A[i] * D[i] % mod;
-    fwtXor(A, false);
-    int Q = read();
+还要预处理$\{i : d |b_{i}\}$进行优化
-    while (Q--) printf("%d\n", A[read()]);
-    return 0;
-}
-</code>
-===== 龙鹏宇 Hardict =====
+[[2020-2021:teams:alchemist:weekly_digest_1:hardict_code1|代码]]
+===== 肖思炀 MountVoom =====
-==== 统计数列中上升子序列个数====
+=== 个人总结 ===
-对应数列$\{a_{i}\}_{i=1}^{n}$
+$NullPointerException$
-考虑一个dp转移:$f[n]=1+\sum_{1\leq i <n,a[i] < a[n]}f[i]$
-可以利用数组数组解决,可是一般数列中会出现相同数,需要预先离散化
-这里有一个技巧,假设数列长度为$n$,可以令$b[i]=(n+1)*a[i]+n-i排序后利用b[]离散化即可得到严格上升下对应的rank\\若令b[i]=(n+1)*a[i]+i则可得到不严格上升的rank$
-=== 例题 ===
-[[http://codeforces.com/gym/101192/problem/A|2015-2016 6th BSUIR Open Programming Contest. Semifinal A题]]
-**题意:**
-给定数列$\{a_{i}\}_{i=1}^{n}$,求所以上升子序列的gcd的和
-**题解:**
-===== 肖思炀 MountVoom =====
 === 其他 ===
@@ 行 176: / 行 80: @@
 === 霍尔定理 ===
-[[2020-2021:teams:alchemist:mountvoom:hallTheorem|霍尔定理]] (题目在补了在补了qwq)
+[[2020-2021:teams:alchemist:mountvoom:hallTheorem|霍尔定理]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具